199 views
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'?
| 199 views
0
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)$.
0
the lower bound on number of function would be O(1) right? for n=0,1

+1 vote

O(2^n) function coll

by Boss (35.1k points)
0

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

check the answers above in image..!

by Active (3.9k points)

1
2