The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
185 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'?
asked in Programming by (33 points) | 185 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

2 Answers

+1 vote

O(2^n) function coll

 

answered by Boss (34.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..

0 votes

check the answers above in image..!

answered by Active (3.9k points)

Related questions

+3 votes
1 answer
3
asked Dec 24, 2017 in Programming by Abhishek Kumar Singh Junior (813 points) | 159 views
+1 vote
1 answer
5
asked Jul 14, 2017 in Programming by gabbar Junior (517 points) | 413 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,481 answers
188,249 comments
74,525 users