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

Instrumentation — where it appears

The counted primitives an algorithm is written against, so that its cost is measured from the run rather than asserted about the code. It is what makes a cost measured from the run rather than asserted about the code, and every algorithm in this collection is written against it.

Named by 4 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 peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

Measuring what an algorithm keeps

Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

space · Space 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 how far the top k movedthe order warninghow far the floors are from doublingthe regime warningstationary Zipf0.160.53 (54%)one key floods a stretch0.170.59 (54%)a heavy hitter that stops0.170.65 (52%)the popular keys drift0.9134.00 (0%)k = 32 · 40,000 arrivalsin brackets: the leaf model at sixty-four shards

The warning that is silent for the right reason

The statistic shipped to warn that a merge prediction is about to fail reads 0.160 on a stationary stream, 0.172 on a bursty one and 0.909 on a drifting one. It was asked to be looked at again because it does not catch a burst. It does not, and the reason is that on a burst there is nothing to catch.

wrong · Merge

Named alongside it

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

Comparison countDeterminismFailure modeHonest limitOperation countReproducibilityAdaptive sortAllocatorAuxiliary spaceBenchmarkingBurstinessCache

All concepts