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

Heap — where it appears

An array read as a nearly complete binary tree in which every parent compares no larger than its children, which puts the extreme at the root. Building one from the bottom is linear where inserting n items one at a time is linearithmic, which is a difference in the order rather than in the operations.

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

110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends

What amortised means

Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.

structures · Structure sparse, fixed average degree10010³10³10⁴10⁵10⁶VworkDijkstra, binary heap — E log EDijkstra, all V queued — V^2dense, fixed density10010⁴10⁵VworkDijkstra, binary heap — V + EDijkstra, all V queued — Ethe class is a property of the sweep as much as of the algorithmwork = scans + visits + relaxations + queue comparisons

Two parameters, one bound, no order

With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.

graphs · Graph Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted

Where an algorithm looks

Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).

machine · Machine adjacency scansrelaxationsqueue comparisonsvisitsBreadth-first14,336Dijkstra, all V queued2,118,656Dijkstra, binary heap56,973Bellman–Ford, all passes50,309,120Prim64,884Kruskal74,008V = 2048, E = 6,144, sparse, fixed average degreeevery segment counted exactly

The queue decides the class, and the pseudocode does not name it

Dijkstra's algorithm is eleven lines of pseudocode with a priority queue in the middle of them. Which queue is not stated, and it is the difference between 56,973 units of work and 2,118,656 on the same graph. Two of the three queues here also fail to fit the class they are famous for, in a regime each.

graphs · Graph 10³10⁴10³10⁴10⁵ncomparisonsbottom-up (Floyd)repeated insertionn from 128 to 65,536, random input, seeded1.21× between the two at the right-hand edge

Building a heap from the bottom

Bottom-up heap construction is Θ(n) and repeated insertion is Θ(n log n), and the second of those is a worst case quoted as a behaviour. On random input, repeated insertion measures linear too — 2.22 comparisons per element against 1.87 — and the famous logarithmic factor never appears. On ascending input it appears in full, and it is a factor of six.

structures · Structure 10⁵10⁶10⁴10⁵comparisonsmispredictions (modelled)Insertion 0%Selection 1%Bubble 29%Merge sort 52%Heapsort 27%Quicksort, first 24%Quicksort, median-3 39%Quicksort, random 27%Shellsort 51%Merge + cutoff 40%Timsort 41%Introsort 32%pdqsort 43%Dual-pivot 37%2-bit counters, no historysquares are the sorts that ship

The branch the machine guesses

Insertion sort does 176 times as many comparisons as Timsort at n = 8,192 and mispredicts a sixth as many branches. Merge sort's inner test is a coin flip and misses 51.5% of the time; selection sort's misses 0.6%. A processor does not wait to learn the answer to a comparison — it guesses, and throws away the work when it guessed wrong — and this is the fifth quantity this site counts.

machine · Machine 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 every orderthe named inputsmean0102030comparisonsInsertion sort7 to 28 · named inputs reach 28Merge sort12 to 17 · named inputs reach 16Heapsort21 to 29 · named inputs reach 27Quicksort, first-element pivot13 to 28 · named inputs reach 28Quicksort, median of three25 to 29 · named inputs reach 2540,320 orders of 8 distinct elements3 worst cases unnamed

A count over every input

Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.

counting · Count 40%60%80%100%8121624324864elements sortedshare of the known worst case the climbs reach, on averageInsertion sort · 20 of 24Merge sort · 24 of 24First-element quicksort · 0 of 24hollow: none reached it24 climbs a size · 100 swaps per elementworst cases known exactly

The worst case found by climbing

A search that swaps two elements at a time and keeps whatever does not lower the count finds the worst case of all five sorts at eight elements, where every answer can be checked. At sixty-four it finds merge sort's worst case every time and reaches 39% of first-element quicksort's — whose worst case is sorted input, the most famous bad input there is. Checking a search where the answer is known certifies it only there.

counting · Count 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

A worst case ten positions wide

Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.

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 1M2M4M16M64Mmean run length, in memoriesrandom33 runssorted1 runreversed64 runssorted, 1% arriving late2 runssorted, 10% arriving late7 runs262,144 records, 4,096 in memorydashed: two memories

Runs twice as long as memory

Feed 262,144 random records through a heap that holds 4,096 and the sorted runs that come out average 1.94 memories — the snowplow's famous factor of two. At a fan-in of 63 that saves a merge pass at 262,144 records, and at two of fourteen sizes in all. Feed the same heap a sorted file with one record in a thousand out of place and it writes two runs instead of sixty-four. And it spends 19 comparisons a record doing so, on every input, where sorting the chunks spends five on sorted data. The factor of two is the least of what the method does.

applied · Transfer Merge sortnone · 55% tiesMerge sort with an insertion cutoffnone · 47% tiesInsertion sortnone · 0% tiesBubble sortnone · 55% tiesShellsort2,014 · 71% tiesHeapsort2,403 · 32% tiesSelection sort1,209 · 24% tiesQuicksort, median-of-three pivot1,428 · 99% tiesequal pairs left out of the order they arrived in4,096 records, 8 distinct keysdark: the sorts that move them

The order equal keys keep

Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.

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.

Worst caseComparison countMerge sortQuicksortExhaustive searchAdversarial inputBenchmark inputDistributionLower boundPriority queueAdjacencyAmortised analysis

All concepts