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

Selection — where it appears

Finding the item of a given rank without sorting the rest, which needs linear time in one pass and far less space in several. It needs linear time in one pass and far less space in several, which makes it the cleanest example of passes and space trading against each other.

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

10³10⁴10⁵10⁶passes over the datapeak bits of stateone pass, exact: 1,048,576 bitsradix, uniformsample, uniformradix, paretosample, paretoevery point exact · 32,768 values320 bits at best

What a second pass buys

Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.

space · Pass universe 0…11 · prefixes of 6 · candidate keeps 9 bitsthe two prefixes that collideA01234567891011B01234567891011first differencesame state — the candidate stores "7" after boththen both read the same suffix -1, -2, 12, 13, 14true median of A3true median of B4and one answer for both924 prefixes · floor ⌈log₂ C(12,6)⌉ = 10 bits10 bits collide on none

A floor one pass cannot get under

An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.

floors · Pass 1101001,00010,00010⁵10⁶k, the elements the caller readscomparisonssort all, read kbuild a heap, pop kselect k, sort thoseincremental quicksortkeep the best k while scanningknockout tournamentdashed: the floorlabels at k = 1,00065,536 random distinct keysevery answer checked

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.

counting · Count 1416642561k2k4k8k16k33k66k11010010³10⁴10⁵10⁶keys handed backcomparisons no method can go underthe losers, and the outputs' ownorderevery element not handed back losesthe answer is one of n!/(n−k)!sequences65,536 keyseach is a claim about every possible method

Two floors that can be added

Handing back the ten smallest of 65,536 keys has two floors under it and neither is close where they cross — the larger of the two is 63,821 comparisons at k = 4,000 and the best method makes 125,401. They can be added, because a comparison that eliminates a key the caller never sees can never be a comparison that orders two the caller does see. Charged together the floor rises 62%, and the tournament goes from 1.97 times it to 1.21.

counting · Count 11010010³10⁴10⁵10⁶k, the number handed backcomparisonstournament, measuredfloor that names the outputsbest earlier floorn = 65,536, one shuffled inputthe floors are worst-case, the count is one input

The comparisons that name the answer

Returning the 4,000 smallest of 65,536 keys in order needs 61,536 comparisons to eliminate the rest and 42,100 to order the ones returned. That was the floor, 103,636, and a tournament made 125,388. What the floor never charged is saying which 4,000 come back. Charge that, and the floor is 125,341. On the same input the tournament is 47 comparisons above it, and for every k up to a hundred it is exactly on it.

counting · Count

Named alongside it

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

Honest limitLower boundComparison countInformation floorOutput-sensitiveWorst caseAdversary argumentComplexity classExhaustive searchFalsificationHeapMeasurement

All concepts