Greedy approach

Problem: What is fib(200)? What about fib(n), where n is any positive integer?


Algorithm 1 fib(n)
if n = 0 then
return (0)
if n = 1then
return (1)
return (fib(n − 1) + fib(n − 2))



Questions that we should ask ourselves.
1. Is the algorithm correct?
2. What is the running time of our algorithm?
3. Can we do better?