Part 7 · 1 chapters · ~8 min

Recurrences

Recurrence relations from recursive code, solving by unrolling, linear recurrences and Fibonacci growth, the cost of naive recursion computed, memoisation, divide-and-conquer recurrences, the master theorem with merge sort and binary search, and amortised analysis of dynamic arrays.

From code to recurrence to growth

code

let calls = 0;
const fib = n => { calls++; return n < 2 ? n : fib(n - 1) + fib(n - 2); };
fib(30); calls                 // 2,692,537

// master theorem, T(n) = a·T(n/b) + f(n), compare f(n) with n^(log_b a):
//   merge sort      a=2, b=2, f=n   → n^1 = f      → O(n log n)
//   binary search   a=1, b=2, f=1   → n^0 = f      → O(log n)
//   naive matrix ×  a=8, b=2, f=n²  → n^3 > f      → O(n³);  Strassen a=7 → O(n^2.81)

// amortised: a dynamic array doubling on overflow copies 1 + 2 + 4 + … + n < 2n elements in total
//   → O(1) amortised per push, though one push occasionally costs O(n)

RECURRENCES: WHY NAIVE RECURSION EXPLODES

function calls to compute fib(30), computed

swipe the figure sideways, or tap expand for full screen

1/4

the recurrence

Naive fib makes T(n) = T(n-1) + T(n-2) + 1 calls, which grows like φⁿ (φ ≈ 1.618). Computing fib(30) made 2,692,537 calls.

T(n) = T(n-1)+T(n-2)+12.69 million calls