Chapter 3, Modularity, Objects, and State

Exercise 3.57


For the memoized part, to compute term, we need additions. Thus it is linear in time complexity.

Without memoization, to compute term, the add-streams take two fib streams(fib and (cdr fib)) and add their first term. Or we add . 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.