You mean invalidation? Speaking of invalidation, the memoized Fibonacci will work even with a cache of 1 item that is replaced each time. (By work, I mean slas

You mean invalidation? Speaking of invalidation, the memoized Fibonacci will work even with a cache of 1 item that is replaced each time. (By work, I mean slash exponential time to linear.) If you calculate fib(n - 2) first and cache it, evacuating everything else in the process, that is good enough: when f(n - 1) needs f(n - 2), it finds it instead of recursing, and so the multply-and-surrender logic is disrupted, resulting in time proportional to n.