Solved

Posted on 2011-05-02

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?

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

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?

10 Comments

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

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

It looks like it would still be O(n), as number of multiplication looks linear

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

thats wrong, should be:

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

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

i thought it is like factorial, I was wrng, sorry

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Java 1603 Error | 2 | 26 | |

scoresIncreasing challenge | 10 | 47 | |

My project did see openJDK that I installed. What could be the problem | 7 | 60 | |

java. non-English characters encoding problem. intellij idea | 3 | 23 |

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

Connect with top rated Experts

**13** Experts available now in Live!