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

Two parameter bound — where it appears

A complexity claim in two quantities at once, which means nothing until the regime relating them is stated. It means nothing until the regime relating the two is stated, because sweeping one at fixed other is a different experiment from sweeping their ratio.

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

11010010³10⁴10⁵10⁶10⁷natural runs r in the inputcomparisonsn / minrun = 256TimsortMerge sortInsertionn + n log₂ rn = 8,192, runs built exactlycomparisons, counted exactly

A run is a property of the input

A benchmark that says "nearly sorted" never says how nearly. It is a recipe with a seed, not a measurement, and an adaptive bound stated against it is a bound with an undefined second parameter. Counting the natural runs turns the shape of an input into a number — and then Timsort's bound becomes something that can be fitted rather than quoted.

practice · Practice 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 10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons

The precondition that removes the queue

Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.

graphs · Graph busiest vertexuniform pairsbusiest 16 · Σd² 43,104 · degeneracy 4attachmentbusiest 114 · Σd² 90,296 · degeneracy 4pairs of neighbours examineduniform pairs — every pair18,480uniform pairs — oriented4,090attachment — every pair42,076attachment — oriented3,339V = 1,024, E = 3,072 on both30 triangles and 249 — the answers, which also differ

Two parameters are not enough either

Two graphs on 1,024 vertices with 3,072 edges each — identical in both numbers every bound in this field is written in. Enumerating every pair of neighbours of every vertex costs 18,480 examinations on one and 42,076 on the other. The quantity that separates them is a third parameter, it is computable in linear time, and it appears in no statement of the problem.

graphs · Graph 0.111010010³10³10⁴floor, in countsarrivals in the shard, nround-robin — n^1.02hashed — fit refusedresidual 2.7%slope 5.2 → 1.19k = 32 · 40,000 arrivalsthe table holds 1.33 of a hashed shard's keys and 0.01 of the stream's

A floor with two variables in it

Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.

floors · Floor 24816326412825510⁶10⁷average out-degreecounted workBellman–Ford from every sourceJohnson's reweightingFloyd–Warshall256 vertices, every answer comparedwork: relaxations + heap comparisons

One Bellman–Ford buys every Dijkstra

A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.

graphs · Graph 01002003004005006007008009001000roundloads 1.0×blockedloads 1.0×hashedloads 17.6×worst error over the heaviest keyschaintreesmallest-firstlargest-first32 shards · k = 32 · 40,000 arrivalseven 1.00× · uneven 2.7×

A parameter that waits for another

Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.

wrong · Merge

Named alongside it

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

Dijkstra's algorithmRegimeBellman–FordCounted primitiveCurve fittingDensityHonest limitMeasurementNegative weightPartitionRelaxationShard

All concepts