Reasoning about cost
You know what the machine and the network charge; algorithms are how you decide what to buy.
You now know what the machine and the network charge. Algorithms are the discipline of deciding what to buy, and big-O notation is its grammar: ignore constants and ask one question — as the input grows, how fast does the cost grow? That single question separates designs that survive success from designs that melt at their first real workload.
The growth classes you actually meet
| Class | Feels like | At n = 1,000,000 | Typical source |
|---|---|---|---|
| O(1) | free | 1 step | hash lookup, array index |
| O(log n) | free enough | ~20 steps | binary search, balanced tree |
| O(n) | one pass | 10⁶ steps — ms in RAM | scan, filter, single loop |
| O(n log n) | a sort | ~2×10⁷ — still fine | sorting, merge joins |
| O(n²) | a wall | 10¹² — hours or never | the accidental nested loop |
| O(2ⁿ) | a proof you need a new idea | — | brute-forcing subsets |
The one to fear is the quiet O(n²): a loop that calls a function that loops — a contains on a list inside a for, an N+1 query pattern, string concatenation in a loop. Fine at n = 100 in the demo, dead at n = 100,000 in production. Most real “it fell over” stories are this row.
The toolbox, by the question you are asking
| You need | Reach for | Cost | Fine print |
|---|---|---|---|
| Find by exact key | hash table | O(1) expected | resizing pauses; no order; hostile keys can degrade |
| Find in sorted data / ranges | sorted array + binary search, or B-tree | O(log n) | the database index, previewed |
| Keep order while inserting | balanced tree / skip list | O(log n) | pointer-chasing — remember Stage 1 |
| Always know the max / top-K | heap | O(log n) per op | top-K of a stream in K memory |
| First-in-first-out / undo | queue / stack | O(1) | the backbone of BFS and DFS |
| Relationships, reachability | graph + BFS/DFS | O(V + E) | shortest paths: BFS unweighted, Dijkstra weighted |
Two refinements keep the grammar honest. Amortised analysis explains why a dynamic array that occasionally doubles is still O(1) per append — the rare expensive step is spread across the cheap ones. And expected vs worst case explains why hashing and quicksort dominate in practice despite ugly worst cases: the bad case is engineered to be rare. Meanwhile the constants big-O hides still exist — an O(n) pass over a contiguous array beats an O(log n) walk through scattered pointers for any n you will actually meet. Theory gives the shape; Stage 1 prices it.
The estimate, worked
The professional habit this stage installs is the back-of-envelope, so do one honestly. Can a single server handle 10,000 requests per second, if each request does two cache reads and one database read?
- Per request: 2 × 0.5 ms (same-DC round trips to cache) + 1 × ~5 ms (DB query) ≈ 6 ms of waiting; CPU work perhaps 1 ms.
- 10,000 req/s × 1 ms CPU = 10 CPU-seconds per second → 10 cores busy: plausible on a 32-core box.
- The 6 ms of waiting costs no CPU if the server is async — but it does hold ~60 requests in flight (10,000 × 6 ms), so memory per request matters.
- The database is now taking 10,000 reads/s — that is the real question, and you found it in four lines of arithmetic.
Same trick for storage: 100 million users × 2 KB of profile ≈ 200 GB — fits on one machine’s SSD easily, fits in RAM on a big one. The point of estimating is rarely the number itself; it is discovering which component is the real problem before you have built the wrong six.
Where it bites
- Optimising before profiling — the slow part is reliably not where intuition points.
- Big-O across the network: an O(n) loop of RPCs is not “linear”, it is n round trips — batch it.
- Small n: for a dozen items, a linear scan of an array beats every clever structure. Constants rule the small.
- Distributing before arithmetic — the estimate above is how you earn the right to stay on one box, which is always the better system.
Free textbook plus problem sets. Rigorous and unusually well written.