Empirical complexity

Memoised Fibonacci

The same recursion as the naive page, with one addition: before working out fib(k), look in a table to see whether it is already there, and write the answer into the table on the way back. Each value is therefore computed once and looked up thereafter, so the call count is 2n − 1 — one call per value computed, plus one immediate return per value looked up. A memo does not make the calls disappear; it makes all but n of them cheap.

The claim being tested

O(n)

When it is the right choice

Whenever a recursion asks for the same subproblem more than once, which is most recursions worth memoising and none worth not. It is usually three lines on top of code that already works, which makes it the cheapest large speed-up in programming. The cost is the table: O(n) memory here, and on a problem with a large sparse subproblem space a memo can be the thing that runs out of room.

How it works

• Make a table of answers, all empty.
• Ask for fib(n).
• If the answer is already in the table, hand it back at once.
• Otherwise work it out from fib(n−1) and fib(n−2), write it into the table, and hand it back.
• Count every ask, whether it was a lookup or a computation.

Worth noticing

• On linear axes this is a straight line, which is what O(n) looks like when it is not being pressed against the floor of a log plot. The second preset puts it on the naive recursion’s axes instead, where the count axis needs six decades and this curve is the one along the bottom.
• The memo-hit counter is the other half of the story: at n = 48 there are 95 calls of which 45 are hits, so almost half of them return without doing anything. Every one of those hits is a subtree of the naive recursion that did not happen.
• The ceiling is 78, and neither gate that sets it is about operation counts. Past fib(79) the values stop being exact in a floating-point number, and the recursion is n deep, so the 131,072 that this subject’s linear cost would otherwise allow overflows the call stack at about 10,000. Two limits no formula in "operations" can see.

Cost

Best

O(n)

Average

O(n)

Worst

O(n)

Extra space

O(n)

n is

the argument to a recursion

Measures

shuffled: up to n = 78

The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.

A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.

Worth comparing

• Naive Fibonacci — The same recursion without the table. Five orders of magnitude apart at n = 32, and the single most persuasive pair of curves in the catalogue.
• Memoised Fibonacci as a call tree — The same algorithm drawn as a tree with the repeated subtrees cut away. That page shows which work disappeared; this one shows how much.
• Naive Fibonacci as a call tree — The recursion drawn as the tree it is, with fib(3) recomputed five times over in plain sight. That page is why the count explodes; this one is how fast.
• Fibonacci as a table — The same computation as a row of cells filled left to right, which is the memo turned inside out. Three tools, one recursion, three different things to notice about it.

All measured subjects