A junior engineer writes a loop to look up a user's recent activity. It works in development. In production, with 50 million users, the lookup takes 800ms and causes timeouts. A senior engineer replaces the loop with a hash table lookup. The junior had studied hash tables. They did not know when to reach for one.
Algorithm selection is a skill separate from algorithm knowledge. You can memorise fifty algorithms and still choose the wrong one. The choice needs a framework — a procedure that maps the problem's constraints to the algorithm family that satisfies them.
This article gives you that procedure.
The four questions, in order
Algorithm selection proceeds through four questions. Order matters. Each answer eliminates families before the next question narrows the choice.
- Input size. How large is N — small (< 10³), medium (10³–10⁶), large (10⁶–10⁹), or very large (> 10⁹)?
- Update frequency. Is the data read-heavy, write-heavy, or balanced?
- Query type. Point lookup, range query, aggregation, path query, or matching?
- Consistency requirement. Is approximate acceptable, or is exact required?
The answers constrain the algorithm family. Simplicity and operational properties pick the final choice.
Step 1 — Set the complexity budget from N
Input size rules out entire families before you write a line.
| N range | Acceptable complexity | Examples |
|---|---|---|
| < 10³ | O(N²) acceptable | Insertion sort, naive matching |
| 10³–10⁶ | O(N log N) required | Merge sort, binary search, B-tree |
| 10⁶–10⁹ | O(N) or O(N log N) | Hash tables, LSM-tree |
| > 10⁹ | O(1) or O(log N) per query | Consistent hashing, Bloom filter, HyperLogLog |
| Unbounded stream | O(1) space per element | Reservoir sampling, sliding window |
The mistake to name here is naive catastrophe. An engineer finds duplicates in a 1M-element list with a nested loop. That is 10¹² operations — several hours. A hash set finishes in seconds. Whenever you write a nested loop over N, ask: what is N in production?
The rule inverts for small N. If N stays under 10³, the simplest correct algorithm is usually the right one. A trie for autocomplete over 500 words is engineering overhead. A sorted list plus binary search matches its speed and needs no dependency.
Step 2 — Split by update pattern
The second question splits read-fast structures from write-fast ones.
Read-heavy, static data: sort once, binary-search every query. Cost O(N log N) at build, O(log N) per query. B-tree or sorted array.
Write-heavy, read-occasionally: append-only log. Writes O(1). Reads scan the log — acceptable when reads are rare, compacted periodically.
Balanced read/write: hash table. Both operations O(1) amortized. No ordering.
At production scale the same split names concrete infrastructure. LSM-trees (RocksDB) give O(1) writes with O(log N) reads after compaction. B-trees give O(log N) reads for the read-heavy path.
Step 3 — Match algorithm to query type
Query type selects the data structure.
- Point lookup — hash table. O(1) when you know the key exactly.
- Range query — sorted array or B-tree. O(log N + k) where k is result size.
- Aggregation / top-K — heap. O(N log k) to build, O(1) to query.
- Path query — graph. BFS for unweighted, Dijkstra for weighted. O(V + E).
- Cardinality on a stream — HyperLogLog. O(log log N) space.
Get this wrong and every request pays for it. A hash table for a range query forces a full scan. A B-tree for a pure point workload pays log N when it did not need to.
Step 4 — Decide on exactness
The fourth question is AT9 — Correctness vs Performance. Exact algorithms are correct but expensive for large N. Approximate algorithms are fast within a bounded error.
Exact cardinality stores every distinct element. At 100M users per day that is gigabytes of memory. HyperLogLog answers within 2% error in kilobytes. For latency percentiles, unique-visitor counts, trending topics, approximate is not a compromise. It is the correct engineering choice.
The engineer's job is to determine whether the error bound is acceptable — not to assume exactness is required.
The meta-tradeoff: AT6 — Generality vs Specialisation
The framework itself is a tradeoff. It sacrifices generality for the sake of deciding. Every algorithm that fits a wider set of problems has worse worst-case performance on any specific one. Specialised algorithms are faster because they exploit the problem's structure. The four questions make that structure explicit.
A general dictionary handles every workload adequately. A B-tree beats it on ranges, a hash table beats it on point lookups, HyperLogLog beats it on cardinality by six orders of magnitude in memory. You cannot get the specialised speed without paying the specialised implementation cost.
Where it fails
FM5 — Latency Amplification. Skip the N question and you ship an O(N²) path that ran in 10ms on a 100-row test set. In production, N is a million. The same path takes minutes. Every upstream caller waits. Every downstream timeout fires. One un-asked question amplifies into system-wide degradation.
FM3 — Unbounded Resource Consumption. The same root cause consumes memory instead of time. An engineer stores every distinct ID for cardinality; the store grows without bound. The production N is always the right N for complexity analysis — never the development N.
FM6 — Hotspotting. An algorithm that performs O(1) amortized can degrade to O(N) worst case on adversarial input. A hash table with a poor hash function collapses every key into one bucket. The framework picks the family; the implementation still has to handle pathological inputs. For adversarial input, use DoS-resistant hashes.
Real systems already run this framework
Database query planners implement algorithm selection automatically. PostgreSQL estimates N from table statistics, reads the query type, weighs update frequency through the cost model, then picks between sequential scan, index scan, bitmap scan, hash join, merge join, and nested loop join. It is the four questions, compiled.
Apache Spark's cost-based optimiser applies the same questions to distributed algorithms: broadcast hash join for small N, sort-merge join for large N, bloom-filter joins when exactness is not required. The engineer controls N estimates through configuration.
Redis exposes the framework as module names. HSET for point lookup at O(1). ZADD and ZRANGE for sorted-set ranges at O(log N). PFADD and PFCOUNT for approximate cardinality at O(1). Picking a module is picking an answer to question four.
The signal that tells you this applies
An algorithm works in development but times out or runs out of memory in production. The N question was never asked. A system uses a complex data structure for a workload that fits in a sorted array. The complexity budget was never applied. Either signal means the framework was skipped — the engineer chose from what they knew, not from what the problem demanded.
Before you write the code, answer the four questions. If you cannot answer them, you do not yet know the problem well enough to implement it. What is the largest N your query planner has ever chosen the wrong join for — and which of the four questions did its estimator get wrong?
The full framework treatment — compression blocks, three-level exercises, and the complete AT/FM mapping — is in Book 2: Algorithm Engineering, Chapter 20 (The Algorithm Selection Framework). Free chapter available at computingseries.com/books/book2.