The Fibonacci function is dened as follows:

F(0) = 1

F(1) = 1

F(n) = F(n1) + F(n2) for n > 2

1. Assume you implement a recursive procedure for computing the Fibonacci sequence based directly on the function dened above. Then the running time of this algorithm can be expressed as: T(n) = T(n1) + T(n2) + 1 Choose from the following asymptotic bounds the one that best satises the above recurrence and explain your selection:

i T(n) = O(n)

ii T(n) = O(n2)

iii T(n) = (cn), for some constant c

iv T(n) = (nn)

2. What specically is wrong with your algorithm? (i.e., what observation can you make to radically improve its running time?)

3. Give a memoized recursive algorithm for computing F(n) eciently. Write the recurrence for your algorithm and give its asymptotic upper bound.