O(2ⁿ) — exponential complexity

This is an absolute abyss. As the input grows, the execution time of the algorithm grows very fast. Doubled the input — doubled the time. And with every further increase, things only get worse.

Example: computing Fibonacci numbers with the naive recursive method

function naiveFibonacci($n) {
    if ($n <= 1) return $n;
    return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
}

At first glance — it's all simple. But every call spawns two new ones. And so on, and on… Remember Fibonacci's rabbits? Here they are, multiplying like crazy.

In real projects, recursive algorithms with exponential complexity are rare, because there is almost always a more efficient approach (dynamic programming, caching results).

← Previous: O(n³) — cubic complexity · Whole series · Next: O(n!) — factorial complexity →

First published in Ukrainian in the Telegram channel “Created to die” on June 26, 2025.