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

Adversarial input — where it appears

An input constructed against a particular implementation's own choices, so the algorithm meets its worst case rather than its typical one. It is usually cheap to construct once the implementation's choices are known, which is why a fixed seed and a published pivot rule are a liability together.

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

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 quicksort on sorted input — comparisonsfirst-element pivot2,096,128random pivot25,318a search tree built from sorted keys — heightbinary search tree2,047treap26a hash table on keys chosen to collide — worst bucketthe low bits of the key2,048multiply–shift, a at random10n = 2,048, bars on a logarithmic scaledeterministic above, randomised below

Expected is not average

Quicksort on 2,048 sorted keys costs 2,096,128 comparisons with a first-element pivot and 25,318 with a random one. A binary search tree on the same keys is 2,047 deep; a treap is 26. A hash table on keys computed against its hash puts all 2,048 in one bucket; one drawn from a family puts at most 10 there. Three problems, one distinction.

bounds · Distribution average 8.001,0242,048bucket, 0 to 255keys in the bucketthe low bits · keys built for this hashworst bucket 2,048 against 8.0

A hash is a family, not a function

Two thousand and forty-eight keys into two hundred and fifty-six buckets. Under a hash that takes the low bits of the key, all 2,048 land in bucket zero and 255 buckets are empty. Under a multiplier drawn at random, the worst bucket holds 11. The keys are the same keys, and they are the multiples of the table size.

randomness · Randomness 1,00010,000110100modulus qverifications in one searchq = 257: 693measuredn / qchosen text: 6%one unit = one character comparison · base 2568 colliding blocks at q = 1,009, none at q = 1,000,003

A match decided by a number

Rabin–Karp replaces a comparison of two strings with a comparison of two integers, and pays for it only when the integers agree by accident. On 65,521 windows at a modulus of 1,009 it verified 79 times against a predicted 64.9. On a text of 1,024 characters chosen with the modulus in hand it verified at 64 windows out of 64 possible, each one costing fifteen of the pattern's sixteen characters — and the closed form is silent about that, because it assumes nobody chose the text.

randomness · Symbol 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 011228101214161820universe size ubits of statea u-bit bitmaplog₂ C(u, u/2)⌈log₂(u+1)⌉, a counterat u = 12: 924 subsets, 8 bitstwo collide → answers 6 and 7floor computed exactly · collision found by exhaustion at u = 12floor 9.85 bits

The floor under a summary

An exact one-pass distinct-counter over a universe of u keys needs at least log2 of u-choose-u-over-2 bits of state — the same counting argument as the sorting floor, applied to memory states instead of outcomes. At u = 12 that is 9.85 bits, and an eight-bit candidate is shown to collide by running all 924 subsets.

floors · Cardinality 1 coefficient13 members2 coefficients169 members3 coefficients2,197 members4 coefficients28,561 members1 key2 keys3 keys4 keys5 keysexact92% gone99% gone100% gone100% goneexactexact92% gone99% gone100% goneexactexactexact92% gone99% goneexactexactexactexact92% goneevery member walked · GF(13) · no tolerance and no seeddegree 1, 2, 3, 4

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.

randomness · Moment every orderthe named inputsmean0102030comparisonsInsertion sort7 to 28 · named inputs reach 28Merge sort12 to 17 · named inputs reach 16Heapsort21 to 29 · named inputs reach 27Quicksort, first-element pivot13 to 28 · named inputs reach 28Quicksort, median of three25 to 29 · named inputs reach 2540,320 orders of 8 distinct elements3 worst cases unnamed

A count over every input

Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.

counting · Count 40%60%80%100%8121624324864elements sortedshare of the known worst case the climbs reach, on averageInsertion sort · 20 of 24Merge sort · 24 of 24First-element quicksort · 0 of 24hollow: none reached it24 climbs a size · 100 swaps per elementworst cases known exactly

The worst case found by climbing

A search that swaps two elements at a time and keeps whatever does not lower the count finds the worst case of all five sorts at eight elements, where every answer can be checked. At sixty-four it finds merge sort's worst case every time and reaches 39% of first-element quicksort's — whose worst case is sorted input, the most famous bad input there is. Checking a search where the answer is known certifies it only there.

counting · Count 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

A worst case ten positions wide

Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.

counting · Count

Named alongside it

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

GuaranteeQuicksortWorst caseDistributionRandomised algorithmBenchmark inputComparison countExhaustive searchHash tableHeapMerge sortPivot

All concepts