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

Treap — where it appears

A binary search tree keyed by the data and heap-ordered by a random priority, whose shape is therefore a random tree whatever order the keys arrived in. Its shape is a random tree whatever order the keys arrived in, which is randomisation moving the bad case from the input to the coin.

Named by 5 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 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 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.

Skip listDistributionGuaranteeAdversarial inputBinary searchBinary search treeComparison countExpected casePivotRandomised algorithmSeeded randomnessAverage case

All concepts