← O(2ⁿ) — exponential complexity
docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards
en/articles/from-tg/series/algorithm-complexity/o-2n.md
new file +26
−0
1
+
# O(2ⁿ) — exponential complexity
2
+
3
+
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.
4
+
5
+
## Example: computing Fibonacci numbers with the naive recursive method
6
+
7
+
```php
8
+
function naiveFibonacci($n) {
9
+
if ($n <= 1) return $n;
10
+
return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
11
+
}
12
+
```
13
+
14
+
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.
15
+
16
+
In real projects, recursive algorithms with exponential complexity are rare, because there is almost always a more efficient approach (dynamic programming, caching results).
17
+
18
+
:::warning
19
+
O(2ⁿ) is a red flag. If you see something like this in production, it's time to sound the alarm and look for an optimisation.
20
+
:::
21
+
22
+
← [Previous: O(n³) — cubic complexity](/articles/from-tg/series/algorithm-complexity/o-n3) · [Whole series](/articles/from-tg/series/algorithm-complexity) · [Next: O(n!) — factorial complexity →](/articles/from-tg/series/algorithm-complexity/o-n-factorial)
23
+
24
+
---
25
+
26
+
*First published in Ukrainian in the Telegram channel [“Created to die”](https://t.me/php_while_true/48) on June 26, 2025.*