Chapter 3, Modularity, Objects, and State

Exercise 3.57


For the memoized part, to compute $\,n^{th}\,$ term, we need $\,n^{th} - 2\,$ additions. Thus it is linear in time complexity.

Without memoization, to compute $\,n^{th}\,$ term, the add-streams take two fib streams(fib and (cdr fib)) and add their first term. Or we add $\,fib_{n-1} + fib_{n}\,$. Now the problem is that unlike in the memoized part this sums are recomputed again! So in a way we are back to our resursive version of fibs that we saw here. There are already saw that this is a exponential time complexity.