fib(n) = fib(n − 1) + fib(n − 2) is short to write but asks for the same smaller values over and over. Remembering each answer the first time (a memo) means every fib(k) is computed once and every repeat is an instant look-up.
- Average time
- O(n)
- Space
- O(n)