Naive Fibonacci
Every Fibonacci number is the sum of the two before it, and written as a direct recursion that means every call makes two more until it reaches a base case. Nothing is remembered, so fib(n−2) is computed once for the fib(n−1) branch and again for the fib(n−2) branch, and so on all the way down. The number of calls is exactly 2·fib(n+1) − 1, which grows by a factor of the golden ratio for every 1 added to n.
The claim being tested
O(2ⁿ)
When it is the right choice
Never, as an algorithm. It is here because it is the clearest exponential a reader can hold in their head, and because it is the standard example of a recursion that recomputes: the fix is either a memo or a table, and both are one page away in other tools. Its practical lesson is about the shape of the recursion tree rather than about Fibonacci, which is rarely the thing anyone actually needs.
How it works
- Ask for fib(n).
- If n is 0 or 1, hand it back; that is a base case.
- Otherwise ask for fib(n−1) and fib(n−2) and add them.
- Count every one of those asks as a call.
Worth noticing
- The measured growth factor is 1.618 per step of n, not 2. O(2ⁿ) is a correct upper bound and a loose one — loose by a factor of about 1,700 at n = 32 — and the tight bound is Θ(φⁿ), with φ the golden ratio. This page reports what it measured rather than what it was told, which is the whole reason a plotter is worth building.
- On a linear x axis against a logarithmic y axis this is a straight line, and its gradient is the logarithm of the growth factor. An exponential and a power law are straight on different pairs of axes, and telling them apart is what the axis control is for.
- The ceiling is n = 32, where the recursion makes 7,049,155 calls. That is not a memory limit or a frame limit: it is a time limit. At n = 34 the whole measured run would take about a fifth of a second of pure counting, and at n = 40 it would take half a minute.
Cost
- Best
- O(φⁿ)
- Average
- O(φⁿ)
- Worst
- O(φⁿ)
- Extra space
- O(n)
- n is
- the argument to a recursion
- Measures
- shuffled: up to n = 32
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.