Part 0 · 2 chapters · ~12 min

Complexity and Amortisation

Counting operations, Big-O, Big-Θ and Big-Ω, the common growth classes with measured examples, worst, average and best cases, space complexity, amortised analysis of dynamic arrays and hash table resizing, and why measurement still matters.

Growth rates, measured

code

// the three duplicate finders from the figure
const quadratic = (a: number[]) => { let d = 0; for (let i = 0; i < a.length; i++) for (let j = i + 1; j < a.length; j++) if (a[i] === a[j]) d++; return d; };
const bySort = (a: number[]) => { const b = [...a].sort((x, y) => x - y); let d = 0; for (let i = 1; i < b.length; i++) if (b[i] === b[i - 1]) d++; return d; };
const byHash = (a: number[]) => { const s = new Set<number>(); let d = 0; for (const x of a) s.has(x) ? d++ : s.add(x); return d; };

class	example	n = 1,000,000 → roughly
O(1)	array index, hash lookup	1 step
O(log n)	binary search, balanced tree lookup	20 steps
O(n)	a single scan	10^6 steps
O(n log n)	good sorting	2 × 10^7 steps
O(n²)	all pairs	10^12 steps: hours
O(2^n)	all subsets	impossible beyond n ≈ 40

THE SAME PROBLEM, THREE GROWTH RATES

finding duplicates among n = 50,000 random numbers, measured on this machine (Node, M3 Pro)

swipe the figure sideways, or tap expand for full screen

1/4

quadratic

Comparing every pair is O(n²): at n = 1,000 it took 1.5 ms, at 10,000 it took 29 ms, at 50,000 it took 727 ms. Five times the data, twenty-five times the work.

n × 5 → time × 251.5 → 29 → 727 ms as n grew

Amortised analysis

A dynamic array (JavaScript array, Python list, Go slice, Java ArrayList) doubles its capacity when full. One push occasionally copies everything (O(n)), but over n pushes the total copying is n + n/2 + n/4 + … < 2n, so each push costs O(1) amortised. Hash tables resize the same way. Amortised cost is an average over a sequence, guaranteed, not a probabilistic average.

code

// why doubling works: total copies over n pushes
capacity: 1 → 2 → 4 → 8 → … → n
copies:   1 + 2 + 4 + … + n/2 = n - 1   → O(n) total, O(1) per push
// growing by a constant (+10) instead: copies 10 + 20 + 30 + … → O(n²) total. Always grow geometrically.

Space complexity counts extra memory: the hash approach uses O(n) memory to save time; the sorting approach can work in place. Time-space trade-offs are the most common design choice in this course.