Recursion

Question

int f (int n){

       if (n==0)

         return 0;

       if(n==1)

         return 1;

else

return f(n-1)+f(n-2);

}

Find the upper bound and lower bound to the number of function calls for input size 'n'?

Comments

upper bound means worst case in that case it will give complete binary tree so no. of function calls $O(2^n)$

lower bound means best case ,this is fibonacci  series program using dynamic program using table no. of function calls will be $\Omega(n)$.

---

the lower bound on number of function would be O(1) right? for n=0,1

Answer 1

O(2^n) function coll

 

Comments

it should be O($\phi$ⁿ) recursive function calls instead of O(2ⁿ)... For number of function calls , we have to solve recurrence which will give  O($\phi$ⁿ) where $\phi$ is golden ratio and  it  is  $\approx$ 1.618..

Answer 2

check the answers above in image..!