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

Rotation — where it appears

A local rearrangement of a search tree that changes its shape and preserves its order, which is how balanced trees stay shallow. It changes a tree's shape and preserves its order, which is how a balanced tree stays shallow without ever rebuilding itself.

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

sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

structures · Structure peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three14log nQuicksort, random pivot32log nQuicksort, first-element4,097nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, already sorted inputone slot = one array element or one stack frame

In place is a claim, and it is usually wrong about quicksort

Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.

wrong · Space 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

Named alongside it

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

GuaranteeBinary searchBinary search treeInsertion orderPivotQuicksortWorst caseAmortised analysisAuxiliary spaceBalanceCacheComparison count

All concepts