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

Determinism — where it appears

The property that the same input produces the same output and the same counts on every run. It is what makes a measurement quotable in a caption, and it is weaker than machine-independence: a routine can be perfectly repeatable and still be a fact about one implementation.

Named by 2 essays across one field — 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 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

Named alongside it

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

Comparison countInstrumentationOperation countReproducibilityAdaptive sortBenchmarkingCacheDistributionFailure modeHonest limitInformation floorMeasured count

All concepts