<< Previous exercise (3.56) | Index | Next exercise (3.58) >>


Every term in fibs is computed first as the sum of two previous terms.  Since fibs is memoized recalling each previous term requires no additions.  Thus each term after the first uses one addition.  To compute the nth term (starting at n=0), max(0, n-1) additions are made.  If we had not memoized fibs, then to recall previous terms in fibs would require each term to be recomputed.  Since the only terms not computed are 1 and zero, fib(n) would require at least fib(n) - 1 additions which is exponential.