About

This is a growing collection of illustrated essays about algorithms and data structures. Each takes a single idea and draws it until the argument is visible — and every count in every figure comes from running the algorithm and counting, not from reading its loops.

No algorithm is called Θ(n log n) here until it has been measured

The usual way a complexity class gets attached to an algorithm is that somebody looks at the nesting of its loops and writes down the answer. That is a sound method and it is not a check on anything: an implementation with a subtle bug has the same loop structure as one without, and both get the same caption.

Here every algorithm is written against an instrumented array. Reading an element, writing one, comparing two, swapping two — each goes through a primitive that increments a counter. Running the algorithm therefore produces an exact operation count, reproducible to the last digit, with no timer and no dependence on the machine that built the page. The count is then taken across three orders of magnitude and fitted against the candidate classes, and the algorithm is granted a class only if the fit holds and the residual is small.

An algorithm whose declared claim does not survive the fit is not drawn with the caption it wants. The build stops.

Two counts, because one of them is not the one that matters

An operation count is exact, machine-independent, and not a running time. The gap between the two is mostly memory: a comparison whose operands are already in cache costs a fraction of a nanosecond, and one that reaches main memory costs a hundred times more. An algorithm doing half as many comparisons in a worse order is routinely slower.

So a second quantity is carried everywhere. The same run that produces the comparison count also produces the sequence of array indices it touched, and that trace is replayed through a cache model — fully associative, a stated number of lines, a stated number of elements per line, least-recently-used replacement. The parameters are printed on every figure that reports a number from the model.

The two counts are independent, and the site would have much less to say if they were not. Ranking the sorting algorithms by comparisons and ranking them by modelled misses gives two different orders, and a figure asserts that it does — if the second count ever became a restatement of the first, the framing would be empty and the build would say so.

The floors are computed, not quoted

No comparison sort averages fewer than log₂(n!) comparisons. The argument is short: a run is a path from the root of a binary decision tree to a leaf, every one of the n! orderings must reach a distinct leaf, and a binary tree with n! leaves has depth at least log₂(n!).

That bound is computed here by summing logarithms — n! overflows a double at n = 171 and the bound is wanted in the thousands — and checked against Stirling's closed form as an independent route. The two agree to better than one part in a million. Every algorithm on the site is then measured against it, and the interesting number is not the class but the distance: merge sort comes within about 2% of the floor at n = 256, and selection sort uses nineteen times as many comparisons.

The assertions have to reject, and the gate proves it

Assertions that accept everything would pass every other check while making the whole premise void. So a site-local gate deliberately breaks things and requires the machinery to notice: a sort with an introduced bug must fail the sortedness check, a set of measurements from a quadratic algorithm must fail the linearithmic fit, a cache model that reported the same misses for sequential and strided access must fail its independence test.

What measurement cannot do

This limit is on the method rather than on the subject, which makes it unusual, and it is stated plainly because every page here depends on it.

No finite measurement establishes an asymptotic claim. A complexity class is a statement about a limit as n goes to infinity. Measurements stop at some n. Every function measured here agrees with infinitely many others that diverge from it beyond the last data point, so the fits on this site are not proofs and are never described as proofs.

What measurement can do, and what it is used for here:

• Refute. An algorithm claiming n log n whose counts fit n² across three decades has a wrong claim or a wrong implementation, and either is worth finding.
• Measure the constant. The notation discards exactly the factor that decides which of two algorithms in the same class does less work, and that factor is a number this site can produce.
• Show the distribution. "On average" is a statement about a distribution, and the average is the least interesting thing in it. The tail is what happens on the bad day.

What else is checked

• Every sort has to sort. A run whose output is not in order is an error, not a measurement. This has caught more mistakes during construction than anything else here — a broken algorithm still produces a perfectly convincing growth curve.
• Every random input comes from a stated seed. A figure built on Math.random() shows different numbers on every build, and a caption quoting one of them is quoting a number the reader's copy of the page does not contain.
• The counters are checked by hand. A primitive that forgot to increment would lower every number uniformly, and every fitted exponent would still come out right, because a constant factor does not change a slope on logarithmic axes. So the counters are verified against a case whose answer is known independently.
• Averages are averages. Where an essay quotes an average-case cost it is the mean of several hundred independent random inputs, and a figure shows the running mean settling so the sample size can be seen to be adequate rather than asserted to be.
• Two routes wherever there are two. The floor by summation and by Stirling; the probe count by closed form and by filling a table; the invariant of a partition checked at every intermediate step rather than argued for once.

Where the models stop

The cache model is not a machine. It has one level, no set associativity, no prefetcher and no write buffer. What it captures is locality — whether an algorithm touches memory in an order hardware can anticipate — and that is enough to explain the effects the essays are about. It does not produce a time and no essay treats its output as one.

Counting a comparison as one operation is a convention. A comparison of two integers and a comparison of two strings cost different amounts, and the count here does not distinguish them. Where that matters the essay says so.

A closed form is often a limit. Knuth's probe-count formula for linear probing describes a table as its size goes to infinity; a table of 256 slots at 95% load comes in almost half below it. That gap is measured on this site rather than assumed away, because a limit is a claim about a sequence and not a prediction for any member of it.

On being wrong

Corrections are welcome and will be made. A curve with a wrong caption looks exactly like a curve with a right caption, which is the entire argument for computing the caption.