| Flatten Nested List |
O(n) — where n = total elements across all nesting levels |
Processing recursive/nested data structures — JSON, XML, file trees, |
| Generate Parentheses |
O(4^n / sqrt(n)) — nth Catalan number |
Generating all valid structures (expressions, trees, paths). Classic |
| Letter Combinations Phone |
O(4^n) — where n = number of digits (worst case: 7 and 9 have 4 letters) |
Cartesian product generation, combinatorial enumeration. Similar |
| Pow X N |
O(log n) |
Any "repeated operation" that can be halved — exponentiation, matrix |
| Tower Of Hanoi |
O(2^n) — number of moves |
Pure recursive decomposition — the canonical example. Demonstrates |