Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: The figure is the run

Every trace here is a real execution and every number in its caption came from that same execution. A picture and its counts cannot disagree, because there is only one of them.
after 0 writes0 cmpafter 32 writes32 cmpafter 64 writes63 cmpafter 95 writes94 cmpafter 127 writes125 cmpafter 159 writes157 cmprandom input, seed stated in lib/count.js157 comparisons in this run Counting

Counting instead of timing

A stopwatch measures the laptop it runs on. A counter measures the algorithm. Every number on this site comes from an array that increments a tally each time it is read, written, compared or swapped — which makes the counts exact, reproducible to the last digit, and identical on every machine that has ever built this page.

 sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10 Structures

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

 Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted What the machine does

Where an algorithm looks

Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).

 three-entry rule (as shipped, 2002–2015)1414101410314103141054+14+10+3+2+4final stack: 14, 10, 5, 414 is not > 10 + 5 — the invariant is brokenfour-entry rule (Java, after the proof)141410141031410333+14+10+3+2+4final stack: 33every triple satisfies the invariantrun lengths 14, 10, 3, 2, 4both outputs are correctly sorted What is taught wrongly

The invariant that was wrong for seven years

Timsort's merge policy is supposed to keep its run stack shallow, and the rule that enforces it inspects the top three entries. In 2015 a group of formal-methods researchers proved that the rule does not imply what it was believed to imply. Thirty-three elements are enough to break it, the array still comes out perfectly sorted, and the defect is in a structure that nothing about the output can show.

 1 — no differencethe whole array reviewed1.03×only this batch reviewed1.22×a block window, which does alias1.48×20,000 arrivals · period 50 · cyclethe instrument reads 1.48 where an alias is known to be What is taught wrongly

The sampler that cannot alias

A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.

 02468101214mean 5.71depthshare of the collectionten revisionstwelve essays75,658 characters · 2,966 phrasesworst 14, mean 5.71 The data that is not a number

The shape of a real history's depth

Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.

 05101520510revisions in the collectiondepthone revision alone: 8worst depthmean depthfourteen revisions of another9 generations added exactly one Structures

One revision, one level

The cap ladder assumed depth is generations of copying. On a real file it is exactly that — one more revision, one more level, nine times running — plus eight levels the first revision already had before any history existed.

 73 characters long24 runsto depth 7270 characters long24 runsto depth 69longest: 73 × "-" at position 11,0162,685 positions below depth 20, 2,685 of them inside a runeight source modules · worst depth 78100.0% in runs What is taught wrongly

The deepest text is punctuation

Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.

All threads