There are multiple paradigms to compute the nth Fibonacci number, ranging from exponential-time recursion to logarithmic-time matrix exponentiation and even closed-form formulas.
The different approaches reveal different approaches used across the board in the study of algorithms.
Each approach highlights different trade-offs in time and space complexity, and analyzing them requires careful reasoning about recurrence relations, dynamic programming states, and asymptotic growth.
| Method | Idea | Time Complexity | Space Complexity | Analysis Notes |
|---|---|---|---|---|
| Naïve Recursion | Directly use definition \(F(n) = F(n-1) + F(n-2)\). | \(O(2^n)\) | \(O(n)\) (stack depth) | Exponential blow-up due to repeated recomputation of subproblems. Complexity derived from recurrence \(T(n) = T(n-1) + T(n-2) + O(1)\). |
| Dynamic Programming (Tabulation) | Iteratively build array from base cases up to \(n\). | \(O(n)\) | \(O(n)\) | Each state computed once, linear scan. Complexity comes from summing constant work across (n) steps. |
| Dynamic Programming (Space-Optimized) | Only store last two values. | \(O(n)\) | \(O(1)\) | Same recurrence, but memory reduced by discarding unused states. |
| Matrix Exponentiation | Use identity: \(\begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix}^n = \begin{bmatrix}F_{n+1} & F_n \ F_n & F_{n-1}\end{bmatrix}\). | \(O(\log n)\) | \(O(1)\) | Fast exponentiation via repeated squaring. Complexity from halving exponent each step. |
| Fast Doubling Method | Use formulas: \(F(2k) = F(k)[2F(k+1) - F(k)])\), \((F(2k+1) = F(k+1)^2 + F(k)^2\). | \(O(\log n)\) | \(O(1)\) | Similar to matrix exponentiation but avoids explicit matrices. |
| Closed-Form (Binet’s Formula) | \(F(n) = \frac{\varphi^n - \psi^n}{\sqrt{5}}\), where \(\varphi = \frac{1+\sqrt{5}}{2}\), \(\psi = \frac{1-\sqrt{5}}{2}\). | \(O(1)\)to \(O(logn)\)depending on arithmetic | \(O(1)\) | Requires floating-point exponentiation; precision errors grow with (n). Complexity analysis assumes constant-time arithmetic, but in practice large (n) requires arbitrary precision. |
Closed-Form Analysis
Binet’s formula is constant-time in theory, but complexity depends on the cost of computing \(\varphi^n\). With floating-point arithmetic, exponentiation is not truly constant for large \(n\). For exact integer results, arbitrary-precision arithmetic introduces hidden costs.
Fast Exponentiation
This comes up a lot in Fibonacci and is a useful general trick.
Fast exponentiation, also known as exponentiation by squaring, is an efficient algorithm to compute \(a^n\) in logarithmic time, rather than the naive linear time. It works by reducing the number of multiplications needed by breaking down the exponent into binary components (powers of two).
Here is a great explanation of how the algorithm works: https://alexanderobregon.substack.com/p/fast-exponentiation-logic-in-java
In pseudo-code form, this is:
int expo(int a, int b) {
int result = 1;
while (b) {
if (b%2==1) {
result *= a;
}
b /= 2;
a *= a;
}
return result;
}