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.