The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
int f (int n){

       if (n==0)

         return 0;


         return 1;


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


Find the upper bound and lower bound to the number of function calls for input size 'n'?
in Programming by (33 points) | 199 views
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

2 Answers

+1 vote

O(2^n) function coll


by Boss (35.1k points)

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

by Active (3.9k points)

Related questions

+3 votes
1 answer
asked Dec 24, 2017 in Programming by Abhishek Kumar Singh Junior (823 points) | 165 views
+1 vote
1 answer
asked Jul 14, 2017 in Programming by gabbar Junior (517 points) | 436 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
50,376 questions
55,840 answers
91,395 users