# What is the running time complexity of the given function?

The following question is one of the questions from an in-class homework assignment page that I don't believe we ever went over:

What is the running time complexity of the given function?
``````
int mystry(int n) {
if ( n == 0 || n ==  1)  return 1 ;
return mystry(n-1)*mystry(n-2) ;
}
``````

Could you also please give me a quick explanation of how this type of proplem is solved?
###### Who is Participating?

Commented:
Its *not* O(n)

> f(4)= f(2)*f(3)=f(0)*f(1)*f(1)*f(1)

thats wrong, should be:

f(4)= f(2)*f(3)=f(0)*f(1)*f(2)*f(1)=f(0)*f(1)*f(0)*f(1)*f(1)
0

Commented:
0

Commented:
It has something to do with how the time growth with n - if it is first order, second order, etc.
This recursive function is kind of close to factorial - I guess time should grow really quickly
Perhapps Wikipedia should help with that:
http://en.wikipedia.org/wiki/Analysis_of_algorithms
0

Commented:
0

Commented:
It looks like it will always return 1, but complexity
f(2) = f(1)* f(0)
f(3) = f(2)*f(1)= f(0)*f(1)*f(1)
f(4)= f(2)*f(3)=f(0)*f(1)*f(1)*f(1)
It looks like it would still be O(n), as number of multiplication looks linear
0

Commented:
@Eindoofus,
are you sure complexity is O(n)?
0

Commented:
>> f(0)                           --> 1 step
>> f(1)                           --> 1 step
>> f(2) = f(1)* f(0)         --> 2 steps
>> f(3) = f(0)*f(1)*f(1)   --> 3 steps
>> f(4) = f(2)*f(3)          --> (2+3) = 5 steps
>> f(5) = f(4)*f(3)          --> (5+3) = 8 steps

So, # steps, written as a sequence is {1, 1, 2, 3, 5, 8, ...}
Do  you recognize this sequence?
It is growing faster than O(n). Do you know how to compute O(n) for this sequence?
0

Commented:
Yes you are right this is Fibonacci series - it is faser than O(n)
i thought it is like factorial, I was wrng, sorry
0

Commented:
Reassign these points to phoffric - that would be fair.
And for the author I think the answer shoul be O(1.6 in power of n)
1.6 is the golden ratio (sqrt(5)+1)/2
This is how fibonacci grows - exponential
0

Commented:
If T(n) is the running time then

T(n)   = O(1),     n=0 or 1

T(n) = T(n-1) + T(n-2) +O(1)   otherwise

T(n) is basically the binomial sequence and hence exponential.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.