1. Consider the following pseudo-code:

AlgorithmFibCache

Inputs: n, an integer >= 0

C, an array of integers

Output: the nth Fibonacci number (and possible changes to C)

1 if capacity(C) <= n then

2 ensure_capacity(C, n) // initialize with zeros

3 if n == 0 or n == 1 then

4 return 1

5 if C[n] 0 then

6 return C[n]

7 C[n] := FibCache(n-1, C) + FibCache(n-2, C)

8 return C[n]

We are interested in the asymptotic complexity of the recursiveFibCache algorthim as the parametern grows. In particular, we want to know T(n) = the number of times we have to perform addition. (Note:ensure_capacity()does no additions.)

1. How many additions are done in the base case? On which line(s) is the test for the base case?

1. How many recursive calls are made? On which lines do they occur?

1. Give T(n) for this algorithm, using either the trees/levels method or the "unfolding" (table) technique.