Seeded randomness — where it appears
Named by 4 essays across 3 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 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.
The independence an estimator spends
Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.
The count of the part that was read
Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.
Named alongside it
The objects these essays reach for when they reach for this one.
Adversarial inputComparison countDistributionRandomised algorithmSkip listTreapWorst caseBinary searchBinary search treeEntropyEstimatorExpected case