02 · Algorithms & Data Structures

This chapter is the floor immediately above computability: 01 says a task can be done at all, and this floor asks what doing it will cost.

Given that it can be computed, how well can it be done?

In 1960, at a seminar he was running at Moscow State University, Andrey Kolmogorov told the room that multiplying two n-digit numbers must cost on the order of n² elementary operations — that the method every schoolchild learns, digit against digit, is essentially the best there is. It was a reasonable thing to believe. Every multiplication algorithm anyone had written behaved that way, and Kolmogorov was not a man whose conjectures were casually wrong.

A student in the room, Anatoly Karatsuba, broke it inside a week. His trick is almost embarrassingly small: cut each number in half. The schoolbook method then wants four half-sized products; Karatsuba noticed that three suffice, because the fourth quantity can be recovered by subtracting the ones you already have. Do that recursively and the cost falls from n² to n^log₂3 — about n^1.585. At the next meeting Kolmogorov reported the refutation himself, and then discontinued the seminar (Karatsuba, The Complexity of Computations, 1995).

Nothing in the world had changed that week. No new machine, no new physics. A fact about cost had been discovered, the way facts about nature are discovered — and that is what this floor studies.

Cost is a shape, not a number. The notation for it was borrowed from number theory: Paul Bachmann introduced big-O in 1894, and Edmund Landau adopted it in 1909, crediting him (MAA Convergence); Donald Knuth's 1976 note in SIGACT News pushed computing to standardize on O, Ω and Θ (Knuth, 1976). Notice what the notation deliberately throws away: constant factors. That is not sloppiness. Constants are the part of the cost that hardware, compilers, and careful coding can move; the growth rate is the part the algorithm itself owns, and no amount of engineering below it will change it. A machine ten times faster buys you a constant. An exponent buys you the future: on Karatsuba's exponents alone, the saving is roughly eighteen-fold at a thousand digits and three hundred-fold at a million.

A small catalogue of strategies covers most of the ground. They are worth knowing by name, because almost every algorithm you will meet is one of them wearing local clothes.

Divide and conquer splits a problem into smaller copies of itself, solves those, and stitches the answers together — Karatsuba's trick, and mergesort, which von Neumann wrote out in 1945 in what survives as the earliest example of his coding (Knuth, "Von Neumann's First Computer Program," 1970). Its most famous application is a three-page paper by Volker Strassen with the flatly provocative title "Gaussian elimination is not optimal," which multiplied matrices in about n^2.807 instead of n³ (Numerische Mathematik 13, 1969). The chase it started has run for over half a century and is still running: the published record now stands near n^2.371 (Alman et al., SODA 2025), and nobody knows how far down it goes.

The greedy strategy takes the locally best step and never looks back — either naive or optimal, depending entirely on whether the problem has the structure that rewards it — and when it does, greed is unbeatable. Dijkstra's shortest-path algorithm is the canonical case, published in three pages in 1959 (Numerische Mathematik 1: 269–271). He designed it, by his own account, in about twenty minutes in 1956, without pencil or paper, sitting on a café terrace in Amsterdam while out shopping with his fiancée (oral history, Charles Babbage Institute, 2001).

When subproblems repeat, dynamic programming says to remember rather than recompute. Richard Bellman developed it at RAND, where he worked from 1948 to 1965, and the name is a deliberate disguise: RAND answered to a Secretary of Defense who, in Bellman's telling, "had a pathological fear and hatred of the word research," so he chose two words nobody could object to (Dreyfus, "Richard Bellman on the Birth of Dynamic Programming," Operations Research 50, no. 1, 2002). The technique is more honest than its name — it is simply the trade of memory for time.

Strangest of the four is randomization, which wins by refusing to be predictable. Tony Hoare devised Quicksort in 1959–60 as a student in Moscow, working on machine translation of Russian, and published it in 1962 (The Computer Journal 5, no. 1: 10–16). Its worst case is quadratic and an adversary who knows your rule can force it every time; choose the pivot at random and that adversary is disarmed, because now they would have to guess your dice.

A data structure is a payment plan. This is the idea that makes the second half of the field cohere. An unsorted array is cheap to add to and expensive to search: you pay at query time, every time. Sorting it is prepayment — one large charge now in exchange for logarithmic lookups forever after. A hash table pays at insertion for near-instant equality lookups but cannot answer "what comes next"; a balanced tree charges a little more per operation and answers ordered questions the hash table cannot. Databases call the same decision an index, and the trade is identical: writes get slower so that reads get faster (chapter 08). Nothing here is free; you are choosing only the currency. And the currency need not be time at all — precompute a lookup table and you have bought speed with memory, which is the space–time trade in its purest form.

Some costs are floors, not failures of imagination. Any algorithm that sorts by comparing elements is, in effect, a decision tree: each comparison branches two ways, and the tree must have a distinct leaf for every one of the n! possible orderings. A binary tree with n! leaves has depth at least log₂(n!), which grows like n log n. So no comparison sort can beat Ω(n log n) — not one that is cleverer, only one that stops comparing. Counting sort escapes precisely because it looks at the values themselves rather than at pairwise comparisons. Notice that this is chapter 01's move — counting what a procedure can possibly distinguish — aimed at cost rather than at possibility.

And the model leaks. Big-O hides constants, and sometimes the constants are the whole story: Lipton and Regan named the class of galactic algorithms — asymptotically superior, never used, because the input size at which they win exceeds anything that exists (2010). Big-O also hides the machine. Two loops with identical asymptotic cost can differ tenfold because one walks memory in order and the other jumps, which is chapter 04's floor leaking upward. And worst case is not typical case, as chapter 01's SAT solvers demonstrate daily. Asymptotic cost is the price on the label; what you pay at the till still depends on the machine.

Connections

Below: 01, which decides what is possible before this floor asks what it costs. Beside it: 03, which supplies the counting that turns log₂(n!) into a genuine information-theoretic bound. Above: 04, where the memory hierarchy decides which constant factors are real; 08, where B-trees are a data structure shaped by the cost of touching a disk; 12, where the training of a model is dominated by exactly the matrix multiplication Strassen attacked.

Open questions

Is the true exponent of matrix multiplication 2? Sixty years of work has moved it from 3 to about 2.371 and stalled far above the obvious lower bound. More broadly: is worst-case analysis still the right instrument, when the algorithms that matter commercially are judged on inputs that are anything but adversarial? And is the catalogue of strategies above complete — or is there a fifth idea, as basic as divide-and-conquer, that nobody has had yet?

Go deeper

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — the reference; §8.1 has the sorting lower bound in full (MIT Press).
• Edsger Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959): 269–271 — three pages, two algorithms, no wasted sentence (PDF).
• Volker Strassen, "Gaussian elimination is not optimal," Numerische Mathematik 13 (1969): 354–356 — three pages that started a fifty-year race (Springer).