2 votes 2 votes 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'? Programming in C recursion functions programming-in-c + – parasghai28 asked Jul 8, 2018 parasghai28 1.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Prateek Raghuvanshi commented Jul 8, 2018 reply Follow Share 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 votes 0 votes Sahil Sawant commented Jul 9, 2018 reply Follow Share the lower bound on number of function would be O(1) right? for n=0,1 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes O(2^n) function coll abhishekmehta4u answered Jul 8, 2018 abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply ankitgupta.1729 commented Jul 15, 2018 reply Follow Share 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 0 votes Please log in or register to add a comment.
0 votes 0 votes check the answers above in image..! Shubham Shukla 6 answered Jul 9, 2018 Shubham Shukla 6 comment Share Follow See all 0 reply Please log in or register to add a comment.