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

Skip list — where it appears

A sorted list with several levels of forward pointers, each level entered by a coin flip, giving a search the shape of a tree with no rebalancing. Its shape is a sequence of coin flips rather than a property of its keys, so its height is a distribution and no rebalancing is ever performed.

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

level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

randomness · Randomness 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 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 10³10⁴10³10⁴10⁵nrandom bitsskip list, one build — ntreap, one build — nreservoir, Algorithm R — n log nn from 256 to 16,384bits charged including rejections

Counting the coin flips

A skip list spends 2.03 random bits per key and a treap spends exactly 32. Reservoir sampling spends 1,356,399 bits on a stream of 65,536 and a better version spends 9,380. None of those numbers appears in any complexity class any of these structures is described by, and none of the site's other three counters can see them.

counting · Count root, priority 0.9651.00.0prioritykey24 keys, sorted insertion, seed 20260810height 8 against an ideal of 4

The priority nobody supplied

Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.

structures · Structure 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 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

Named alongside it

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

DistributionTreapGuaranteeRandomised algorithmPivotAdversarial inputBinary searchBinary search treeComparison countDerandomisationExpected caseGeometric distribution

All concepts