Naive recursion (exponential) vs DP loop (O(n)) vs Fast doubling (O(log n))
| Method | Time | Space | Mults / bit | Use when |
|---|---|---|---|---|
| Naive recursion | O(φn) | O(n) | — | never (teaching) |
| DP loop | O(n) | O(1) | — | n up to ~106 |
| Matrix exponentiation | O(log n) | O(1) | ~8 | any linear recurrence |
| Fast doubling | O(log n) | O(log n) | ~3 | plain Fibonacci, huge n |