When Work Doubles
O(2ⁿ) means exponential time: one extra input element doubles the work. This is the growth class where algorithms stop being usable — not for huge inputs, but already for medium ones.
Exponential work usually comes from recursion that branches: a function that calls itself twice, and each of those calls itself twice again. The calls form a tree that doubles at every level.
Recursive Fibonacci
The Fibonacci sequence starts 0, 1, and every next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, …
The definition translates directly into a recursive function: fib($n) returns fib($n - 1) + fib($n - 2). It is short and correct — and exponential, because every call spawns two more, and the same values are computed again and again. fib(2) alone is recomputed thousands of times in a bigger call.
Fibonacci with recursion
A counter passed by reference counts every call. Computing fib(10) = 55 takes 177 calls — for one small number. The call tree doubles at every level.
Output: PHP script
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
$calls = 0;
echo "fib(10) = ", fib(10, $calls), "\n";
echo "function calls: ", $calls, "\n";
Why It Explodes
Watch the call count as n grows by steps of 5. It does not grow by steps — it multiplies. Every +1 on n roughly ×1.6 on the calls; every +5 more than ×10.
At n = 50 the count would pass 40 billion calls. That is the exponential trap: the code looks innocent, and small tests finish instantly.
Count the calls as n grows
From fib(5) to fib(25) the input grows 5 times — the number of calls grows more than 16,000 times, from 15 to 242,785.
Output: PHP script
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
foreach ([5, 10, 15, 20, 25] as $n) {
$calls = 0;
fib($n, $calls);
printf("fib(%2d) -> %7d calls\n", $n, $calls);
}
The Fix: A Loop
The problem is not Fibonacci — it is computing the same values over and over. A loop that walks up from 0 and 1, keeping just the last two values, computes each number exactly once.
That is O(n) time and O(1) space: 24 steps instead of 242,785 calls for fib(25). Same answer, a different growth class — this is what algorithm analysis is for.
Fibonacci with a loop
Two variables walk up the sequence; each round computes one new number. fib(25) = 75025 in 24 steps — the recursive version needed 242,785 calls for the same answer.
Output: PHP script
<?php
$n = 25;
$steps = 0;
$a = 0;
$b = 1;
for ($i = 2; $i <= $n; $i++) {
[$a, $b] = [$b, $a + $b];
$steps++;
}
echo "fib(25) = ", $b, "\n";
echo "loop steps: ", $steps, "\n";