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

Redundancy — where it appears

The gap between what a representation costs and what the thing it represents carries. A Huffman code's is bounded by the most probable symbol's share plus a constant, which is why a tree over a skewed distribution sits above the entropy rather than on it.

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

0%25%50%75%Merge sort0.0% · 1.03× the floorQuicksort, random pivot0.0% · 1.16× the floorQuicksort, first-element pivot0.0% · 1.18× the floorMerge sort with an insertion cutoff0.0% · 1.31× the floorInsertion sort0.0% · 9.83× the floorShellsort9.8% · 1.31× the floorQuicksort, median-of-three15.4% · 1.18× the floorHeapsort26.2% · 1.45× the floorBubble sort49.2% · 9.83× the floorSelection sort59.9% · 7.77× the floorshare of comparisons whose answer was already implied256 elements, random orderlight: repeats nothing

The questions a sort asks twice

Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.

counting · Count 32641282565121010010³10⁴elements sortedword operations a comparison must cost to break evenSelection sort, pairsSelection sort, closureBubble sort, pairsBubble sort, closureHeapsort, pairsHeapsort, closureQuicksort, median-of-three, pairsQuicksort, median-of-three, closuresolid: pairs asked · dashed: everything impliedrandom input · counted exactly

The price of remembering an answer

Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.

counting · Count errors, by piecetaken by(0, 0, 0)1(0, 0, 1)1(0, 0, 2)1(0, 1, 0)1(0, 1, 1)1(0, 2, 0)3(1, 0, 0)2(1, 0, 1)2(1, 1, 0)3(2, 0, 0)30 of 10 covered more than once · the numbers are the searchesk = 2 · 3 pieces10 distributions

A schedule nobody writes down

A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.

wrong · Distance 024bits a symbolequalzipftwoSizesoneLargeone bit a symbolentropyplain vectorscompressed blocks32 documents1.26x on the skewed collection

A code word is at least one bit

A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.

bounds · Index

Named alongside it

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

Comparison countLower boundPartial orderSelection sortTransitivityApproximate matchingBidirectional indexBreak-evenBubble sortCompressed bit vectorCost modelCounting convention

All concepts