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) ;
           }

Open in new window


Could you also please give me a quick explanation of how this type of proplem is solved?
EindoofusAsked:
Who is Participating?
 
objectsCommented:
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
 
for_yanCommented:
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
Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

 
for_yanCommented:
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
 
phoffricCommented:
@Eindoofus,
are you sure complexity is O(n)?
0
 
phoffricCommented:
>> 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
 
for_yanCommented:
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
 
for_yanCommented:
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
 
GwynforWebCommented:
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.

All Courses

From novice to tech pro — start learning today.