Geometric distribution — where it appears
Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.
A structure made of coin flips
Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.
The height is a distribution, and the coin is a parameter
A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.
The spread a merge sort does not have
On 65,536 random keys quicksort's comparison count has a standard deviation of 42,470 and merge sort's has one of 141.9 — three hundred times smaller, on means only a quarter apart. Merge sort's count is a fixed bill minus 65,535 independent leftovers, one per merge, each worth about a coin toss, so its spread grows as the square root of n where quicksort's grows as n. From 256 keys up a single run of merge sort pins its mean to one per cent, and a third of quicksort's whole spread is decided by its first pivot.
Named alongside it
The objects these essays reach for when they reach for this one.
DistributionComparison countSkip listBenchmarkingBinary searchBinary search treeConcentrationExpected caseExpected valueMeasurement designMerge sortParameter choice