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

Reproducibility — where it appears

The property that the same input gives the same count on every build, without which no measurement in a caption can be checked. Without it no measurement in a caption can be checked, which is why every random source here is drawn from a stated seed.

Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.

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 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.

counting · Count first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case

What randomising the pivot buys

Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable.

wrong · Distribution keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order

The order nobody fixed

The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.

structures · Merge average 8.001,0242,048bucket, 0 to 255keys in the bucketmultiply–shift · keys built for this hashworst bucket 2,048 against 8.0

The adversary who knows the seed

Every randomised figure on this site is drawn from a stated seed, so that the numbers in the captions are the numbers on the reader's screen. That is also the exact condition under which none of the guarantees those figures demonstrate applies. A published seed is a published function.

wrong · Distribution the language's sortMerge sortlog₂(n!)random43,810 / 43,976nearly sorted10,806 / 24,845already sorted4,095 / 24,576reversed4,095 / 24,576few distinct values27,561 / 42,338n = 4,096, counted through the comparatorthe first column is a fact about the engine, not about sorting

The count that came from somewhere else

Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.

counting · Count 2585167741,032020,00040,000arrivals so farcountSpace-Saving's floorMisra-Gries's decrementsboth 93840,000 prefixes, 0 disagreementsk = 32 against k = 31

Two structures that are one

Space-Saving never underestimates and Misra-Gries never overestimates, and they are taught as rival structures with opposite failure modes. Subtract one number from every Space-Saving counter and what is left is the Misra-Gries table, key for key and count for count, at all twenty thousand prefixes of a stream and at every table size tried.

wrong · Sketch

Named alongside it

The objects these essays reach for when they reach for this one.

GuaranteeComparison countDistributionAdversarial inputDeterminismHash tableHeavy hitterInstrumentationMergeable summaryMisra–GriesOperation countPivot

All concepts