Consider the following pseudo-code: Algorithm FibCache Inputs: n, an integer >= 0 C, an array of integers
Fantastic news! We've Found the answer you've been seeking!
Question:
- 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.)
- How many additions are done in the base case? On which line(s) is the test for the base case?
- How many recursive calls are made? On which lines do they occur?
- Give T(n) for this algorithm, using either the trees/levels method or the "unfolding" (table) technique.
Related Book For
Logic And Computer Design Fundamentals
ISBN: 9780133760637
5th Edition
Authors: M. Morris Mano, Charles Kime, Tom Martin
Posted Date: