Fibonacci, bottom-up
Every Fibonacci number is the sum of the two before it, and that is a recurrence with two base cases: F(0) is 0 and F(1) is 1. Written as a recursion it recomputes the same subproblem an exponential number of times. Written as a table it does not: fill the two base cases, then walk left to right, and each cell needs only the two cells immediately behind it, which are already there by the time you reach it.
Its recurrence
F(i) = F(i−1) + F(i−2)
When it is the right choice
The technique, rather than this particular sequence, is what to take from this page: whenever a problem has a recurrence whose subproblems repeat, a table over those subproblems turns exponential work into linear work. Fibonacci itself is rarely the thing you actually need, which is why it is a good place to learn the shape — the recurrence is two terms wide and there is nowhere for the idea to hide behind the arithmetic.
How it works
- Make a row of cells, one for every number from 0 up to n.
- Write 0 into the first cell and 1 into the second: those are the base cases, and they are not computed from anything.
- Move to the next cell and read the two cells immediately behind it.
- Write their sum into the cell.
- Repeat until the last cell is filled; that cell holds the answer.
Worth noticing
- Watch the two arrows rather than the numbers. Every cell in this table depends on exactly the same two neighbours, which is why the fill order can be as simple as left to right — the dependencies are already behind you.
- The two base cases are filled without any arrows at all, and that is what makes them base cases rather than a special case of the recurrence.
- There is no traceback on this page, and that is honest: the answer is a number in the last cell, not a path. Every other page in this tool has one, and the contrast is worth noticing.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(n)
- Table
- one dimension
- Accepts
- n from 1 to 20
The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.
An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.