The n-th Fibonacci Fn is defined recursively as Fn = Fn-1 + Fn-2, where F0 = 0 and F1 = 1. A naive recursive algorithm for solving this problem is given by REC-FIB (n) if n = 0 then return 0 else if n-1 then return 1 else return (REC-FIB(n-1) + REC-FIB (n-2)) Give a tight asymptotic bound on the worst-case running time of this recursive algorithm. (Hint: Draw the recursive calls tree and count the number of subproblems that will appear on it.) Show how to use dynamic programming to devise an O(n) algorithm for computing the n-th Fibonnacci number.
Explanation / Answer
Very simple answer: a) if you draw a tree (I will attmpt a bit): Fib(5) Fib(4) (Fib(3) Fib(3) (Fib(2) Fib(2) (Fib(1) You can see that it grows like a recursive binary tree. At each level you get twice as many calls as in the level above, and you finish at depth 0, so in general you have 2^n calls (and complexity as well) b) Iterative O(n) algo int fib(int n){ int prev = 0; int curr = 1; if(n == 0) return prev; int count = 1; while(count