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

Randomised algorithm — where it appears

An algorithm whose behaviour depends on coin flips it makes rather than on its input alone, so its cost is a distribution rather than a number. Its guarantee holds on every input rather than on most of them, which is the thing randomisation actually buys and is not the same as being faster.

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

0.1bits the register neededrelative errora = 2a = 1.5a = 1.2a = 1.1a = 1.05a = 1.02√((a−1)/2), predicted200 runs per base · n = 20,000 · exact counter needs 15 bits72.6% at 5 bits

Counting past what the register holds

Morris's counter counts ten million events in five bits by incrementing with probability 2 to the minus c. The estimate is exactly unbiased at every n, its relative error is 71%, and the base is a dial that trades one against the other at a rate of the square root of half of a minus one.

streaming · Sketch share of nodespredictedlevel 149.68% · 50.00%level 225.29% · 25.00%level 312.52% · 12.50%level 46.24% · 6.25%level 53.08% · 3.13%level 61.64% · 1.56%level 70.79% · 0.78%level 80.34% · 0.39%20,000 nodes, p = 0.5, seed 5150worst departure 0.32 points

The height is a distribution, and the coin is a parameter

A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.

randomness · Randomness 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 k/n = 0.1250.0810.1250.169position in the streamshare of runs in which it was sampledAlgorithm R, n = 32, k = 4, 40,000 runsworst departure 3.3% · noise 1.4%

One pass, k slots, and two randomness budgets

Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.

randomness · Randomness 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 with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

The adversary who hides the edge

The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.

floors · Floor randomised pivot164 random bits2.96 ±23%median of mediansno random bits7.94 ±2%0.04.38.6comparisons per element — bar is the range over seeds, tick is the mean30 seeds, n = 4,001, median2.68× the mean, 14× the spread

What derandomising costs

Randomised selection finds the median of twenty thousand elements in 3.21 comparisons per element and median-of-medians takes 8.15 — two and a half times as many for the same answer, both linear. The number that decides between them is not either of those. It is that the first varies by 28% from seed to seed and the second by 1.6%.

bounds · Distribution 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 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures

The estimate that is a median of means

An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.

randomness · Sketch 0.0000.0100.0200.030150200comparisonsprobability per comparison countmean 139.86exact400 runsn = 32, pivot chosen uniformlysampled mean 140.19

A distribution computed rather than sampled

Quicksort with a random pivot makes a random number of comparisons, and every plate on this site reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.

counting · Count 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

Named alongside it

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

DistributionGuaranteeAdversarial inputPivotSkip listVarianceWorst caseComparison countQuicksortRelative errorAverage caseClosed form

All concepts