Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 422
  • Last Modified:

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?
0
Eindoofus
Asked:
Eindoofus
2 Solutions
 
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
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
 
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
 
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

Featured Post

Become an Android App Developer

Ready to kick start your career in 2018? Learn how to build an Android app in January’s Course of the Month and open the door to new opportunities.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now