Large Big-O examples

Big-O at scale: putting it together

A closing look at complexity — this time across everything you've learned. The point is to feel how the choice of data structure and algorithm changes what's possible.

The ladder of complexities

From fastest-growing-slowest to worst, for input size n:

Complexity	Name	Typical source
O(1)	constant	hash lookup, array index, stack push
O(log n)	logarithmic	binary search, balanced BST/heap operation
O(n)	linear	a single scan, BFS/DFS over a list
O(n log n)	log-linear	good sorting, divide-and-conquer
O(n²)	quadratic	nested loops, all pairs
O(2ⁿ), O(n!)	exponential	unpruned subsets / permutations

What it means in practice

At n = 1,000,000:

O(n) ≈ a million steps — instant.
O(n log n) ≈ 20 million — still fast.
O(n²) ≈ a trillion — minutes to hours.
O(2ⁿ) — not in the lifetime of the universe.

The jumps are enormous. That's why "use a hash map instead of a nested loop" (O(n²) → O(n)) or "memoize" (O(2ⁿ) → O(n)) aren't micro-optimisations — they're the difference between a program that runs and one that doesn't.

The recurring moves

Almost every speed-up in this course was one of these:

Trade memory for time — a hash set/map turns repeated scans into O(1) lookups.
Avoid repeated work — memoization / tabulation reuses subproblem answers.
Exploit structure — sorted data unlocks binary search and two pointers.
Explore by distance — BFS gives shortest paths for free.

When a solution works but feels slow, name its complexity, find the dominant cost, and ask which of these moves removes it. That instinct is what you take away from this course.