juniorFibonacci Series

How do you compute large Fibonacci numbers efficiently?

Updated Feb 20, 2026

Short answer

Naive recursion is O(2ⁿ) and unusable past about n = 40. Iterating with two rolling variables is O(n) time and O(1) space, which handles most needs. For very large n, fast matrix exponentiation or fast doubling computes F(n) in O(log n) multiplications — though for arbitrary-precision integers the true cost also depends on the size of the numbers themselves.

Deep explanation

Python
def fib_naive(n):                  # O(2^n) — recomputes the same values endlessly
    return n if n < 2 else fib_naive(n-1) + fib_naive(n-2)


def fib_iter(n):                   # O(n) time, O(1) space — the practical default
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fib_naive(35) makes roughly 30 million calls; fib_iter(35) makes 35 iterations. The naive version's call tree has about 2ⁿ nodes because fib(n-2) is recomputed inside fib(n-1), all the way down.

O(log n) via fast doubling, derived from matrix identities but avoiding the matrix bookkeeping:

TypeScript
F(2k)   = F(k) * (2*F(k+1) - F(k))
F(2k+1) = F(k)^2 + F(k+1)^2
Python
def fib_fast(n):                   # O(log n) arithmetic operations
    def helper(n):
        if n == 0:
            return (0, 1)
        a, b = helper(n >> 1)      # a = F(k), b = F(k+1)
        c = a * (2*b - a)          # F(2k)
        d = a*a + b*b              # F(2k+1)
        return (d, c + d) if n & 1 else (c, d)
    return helper(n)[0]

Equivalent in complexity to raising [[1,1],[1,0]] to the nth power by repeated squaring, but with fewer multiplications per step.

The complexity caveat that interviewers probe. These bounds count arithmetic operations, not bit operations. F(n) has roughly 0.694n digits, so the numbers themselves grow linearly in n. Adding two of them is O(n) bit operations, which makes the iterative method O(n²) in bit complexity, not O(n). Fast doubling multiplies rather than adds, and multiplication of huge integers is superlinear — so the practical crossover between iterative and fast doubling is higher than the O(n) versus O(log n) comparison suggests, typically somewhere in the tens of thousands.

Binet's formula — F(n) = (φⁿ − ψⁿ)/√5 — is O(1) in principle but relies on floating point and loses accuracy past about n = 70. It is a mathematical curiosity here, not a practical method.

Memoisation turns the naive recursion into O(n) and is worth knowing as the general technique, but the iterative version achieves the same complexity in O(1) space with no recursion depth limit.

Real-world example

Where each method stops being usable:

TypeScript
n = 30       naive       ~1.3M calls          ~0.3 s
n = 40       naive       ~200M calls          ~30 s      <- unusable
n = 40       iterative   40 iterations        instant
n = 1,000    iterative   1,000 iterations     instant     (209 digits)
n = 1,000,000 iterative  1M iterations        ~15 s       (208,988 digits)
n = 1,000,000 fast doubling  ~20 recursions   ~1 s

Note the last two rows: fast doubling wins at a million, but not by the millionfold factor the O(n) versus O(log n) comparison implies — because each of those ~20 steps multiplies numbers with hundreds of thousands of digits.

Common mistakes

  • - Using naive recursion beyond about n = 35, where the exponential call tree makes it unusable.
  • - Quoting O(n) and O(log n) without noting they count arithmetic operations on numbers that themselves grow linearly in n.
  • - Using Binet's formula for exact results
  • floating-point error makes it wrong beyond roughly n = 70.
  • - Memoising with a dictionary but still recursing, hitting the recursion limit for large n where iteration has no such bound.
  • - Assuming a fixed-width integer type suffices — F(93) already overflows a signed 64-bit integer.
  • - Being inconsistent about indexing
  • whether F(0) is 0 or 1 shifts every subsequent value and is a frequent off-by-one source.

Follow-up questions

  • Why is the iterative method O(n²) in bit complexity?
  • How does matrix exponentiation compute Fibonacci in O(log n)?
  • When would you use memoisation instead of iteration?
  • Why does Binet's formula fail for large n?

More Fibonacci Series interview questions

View all →