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;
}