Consider the following (incomplete) java code, which calculates the Fibonacci numbers
public int fib(int n){
function++;
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
Let Step(n) denote the number of function calls that the program uses to calculate Fib(n).
The question asks:
It can be shown that Step(n) is roughly $1.61^n$
Consider a computer C that can make 1, 000, 000 function calls a second. Calculate how long time it will take the program to compute Fib(100). A rough estimate is sufficient. hint: You may use the fact that a year (of 365 days) has 31, 536, 000 seconds.
How would you go about working this out? If say fib(1) makes 1 function call, while fib(2) makes 3 function calls and then fib(3) makes 5 function calls etc...How on earth would you work out how many Fib(100) makes? Surely this number is going to be huge!
I of course could use a computer but it's a written question. Some advice/guidance would help as I don't want the answer, just a nudge in the right direction!
fib(n), then we have the following recurrence $F(n)=1+F(n-1)+F(n-2)~\forall~n\geq 2$. Try to solve this recurrence for the closed form of $F(n)$. – learner Apr 21 '16 at 17:16