Solved

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

Posted on 2011-05-02
419 Views
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?
0
Question by:Eindoofus

LVL 47

Expert Comment

0

LVL 47

Expert Comment

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

LVL 47

Expert Comment

0

LVL 47

Expert Comment

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

LVL 31

Expert Comment

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

LVL 92

Accepted Solution

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

LVL 31

Assisted Solution

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

LVL 47

Expert Comment

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

LVL 47

Expert Comment

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

LVL 31

Expert Comment

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

## Write Comment

Please enter a first name

Please enter a last name

We will never share this with anyone.

## Featured Post

### Suggested Solutions

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
"Disruption" is the most feared word for C-level executives these days. They agonize over their industry being disturbed by another player - most likely by startups.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

#### 759 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!