Fibonacci
Dynamic ProgrammingavgO(n)worstO(n)spaceO(n)
0
1
2
3
4
5
6
7
8
9
10
11
12
F(i)
Make a table of 13 cells: cell i will hold F(i)
1 / 15
n12
How it works
Computes F(n) bottom-up: write down the base cases F(0) = 0 and F(1) = 1, then fill each cell as the sum of the two before it. Naive recursion recomputes the same subproblems an exponential number of times; the table solves each one exactly once.
Complexity
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)