Here's the dynamic programming solution in O(n) time. It is also possible to do a bottom-up approach with constant space, but this solution is simpler: var m := map(0 → 0, 1 → 1) function fib(n) if map m does not contain key n m[n] := fib(n − 1) + fib(n − 2) return m[n]