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

Counted work against V, sparse, fixed average degree

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Counted work against V, sparse, fixed average degreeEvery counted operation, summed, on logarithmic axes. The lines fan out because the algorithms differ in class rather than only in constant — at V = 64 the spread between best and worst is 108.1× and at V = 2048 it is 3509×. On this sweep E is proportional to V, so V, E and V + E are the same line and the picture cannot tell them apart.10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

Counted work against V, sparse, fixed average degree

Every counted operation, summed, on logarithmic axes. The lines fan out because the algorithms differ in class rather than only in constant — at V = 64 the spread between best and worst is 108.1× and at V = 2048 it is 3509×. On this sweep E is proportional to V, so V, E and V + E are the same line and the picture cannot tell them apart.

Drawn at 690 × 420, wide on the page. Everything above is what graph-growth returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

20 essays call graph-growth. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons Two parameters

Counting on a graph

 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

Two parameters, one bound, no order

 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 Two parameters

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

 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 Two parameters

The precondition that removes the queue

 adjacency scansrelaxationsqueue comparisonsvisitsKosaraju, two passes5,632Tarjan, one pass2,560V = 1024, E = 1,536, directed, components plantedevery segment counted exactly Two parameters

Two passes or one, and what the second one costs

 No estimate543 cells expanded · path 58Straight-line estimate325 cells expanded · path 58Estimate doubled71 cells expanded · path 64V = 900, E = 895, every edge costs onethe estimate is a function of the vertex, supplied by the caller Two parameters

The precondition on a function the caller writes

 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

Two parameters are not enough either

 10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapBellman–FordBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons Two parameters

The bound with a precondition

 24816326410⁵10⁶components the graph is built fromcounted workcomponents firstBellman–Ford, early exitBellman–Ford, every passV = 1,024, negative arcs between componentsvertices relabelled at random Two parameters

A graph is as hard as its largest cycle

 cells expandedreads building the estimateNo estimate1,572 expanded · path 356Straight-line estimate1,550 expanded · path 356A*, landmarks252 expanded · path 356 · 6,328 reads to buildV = 2,500, steps cost one to nine, seed 20260910shortest path 356 Two parameters

An estimate borrowed from an easier problem

 cells expandedNo estimate543 expanded · path 58Straight-line estimate325 expanded · path 58Dijkstra, reduced costs325 expanded · path 58 · 0 arcs priced below zeroV = 900, unit steps, seed 20260910shortest path 58 Two parameters

An estimate is a reweighting

 stop where they meetextra path length42321stop when keys reach itextra path length110203040grid, by seedV = 900, 28% blocked, steps cost one to nine5 of 40 wrong under the meeting rule Two parameters

Where two searches should stop

 ordered by degreedegeneracy orderthe degeneracy024681012largest out-degreeuniform pairs, degree 452 above duniform pairs, degree 6136 above duniform pairs, degree 1083 above dpreferential attachment, degree 414 above dpreferential attachment, degree 622 above dpreferential attachment, degree 1058 above d1,024 verticesdashed: the degeneracy Two parameters

A bound right for the wrong reason

 steps cost one to ninesteps cost one01,0002,0003,000cells expanded, mean over the gridsA* from one endalways shortestalways shortesttwo-ended Dijkstraalways shortestalways shortesttwo A*, separate estimateswrong on 12always shortesttwo A*, stop on either keyalways shortestalways shortesttwo A*, averaged potentialalways shortestalways shortest40 grids a bar, 2,500 cellsestimate: straight-line cells Two parameters

Two estimates that must agree

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

One Bellman–Ford buys every Dijkstra

 0200400600800cells expanded per query, meanno landmarks897four near the centre423four at random209farthest-first141the corners1268 maps × 150 queriesdots: each map's mean Two parameters

Where the landmarks stand

 125102050100200100observed queries the selection sawcells expanded, meanon fresh querieson the sample it was chosen fromthe cornersfarthest-first8 maps × 150 fresh queriesflat lines read no queries Two parameters

What the queries know that the map does not

 0.000.250.500.751.0005001,0001,500by key60% forward70% forward80% forward90% forwardone-endedhow the expansions are sharedcells expandedseparate key ÷ route40 grids, 2,500 cellsdashed: how close the separate key got to firing Two parameters

A stop that is correct and never sooner

 0396,049792,0981,188,1481,584,1970326496128queries answeredcounted work, cumulativebreak-even at 2.7 queriesBellman–Ford from each sourceone reweighting, then Dijkstra256 vertices, 2,009 arcsanswers compared entry by entry Two parameters

How long a reweighting stays true

 00.50011.50arcs redrawn between queriesstored potential ÷ Bellman–Ford per query0.02%0.1%0.5%2%5%20%recomputed from nothingmended from the broken arcs256 vertices, 128 queriesarc costs redrawn Two parameters

A potential mended where it broke

The library, page 2 of 5 — where graph-growth sits