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

Benchmark input — where it appears

An input a benchmark runs every algorithm on, such as sorted, reversed, nearly sorted or random data. Each was added to catch a failure some algorithm once had, so a fixed list measures the failures it was built against and can miss a new algorithm's worst case.

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

46810120.010.1bits per element (m / n)false-positive ratemeasured(1 − e^(−kn/m))^kfrom the bits set60,000 absent-key queries per point, seed 80800 false negatives at every size

The formula everybody sizes filters with

Fill a Bloom filter with four thousand random keys and its measured false-positive rate is within 4% of the textbook formula. Fill the same filter with the integers 1 to 4,000 and the rate is 30% worse than the formula says — not because the hash is bad, but because it is too good on that input.

wrong · Randomness 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.

Adversarial inputExhaustive searchHeapMerge sortQuicksortWorst caseComparison countCounterexampleDistributionBenchmarkingBloom filterClosed form

All concepts