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

Traversal — where it appears

A systematic visit of every vertex reachable from a start, whose order is decided by the container holding the frontier rather than by the graph. Its order is decided by the container holding the frontier rather than by the graph, which is the choice a pseudocode usually leaves unnamed.

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

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

Counting on a graph

An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.

graphs · Graph peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

Measuring what an algorithm keeps

Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

space · Space 10010³1010010³nstack framesa stack of 512 framespivot: first-elementpivot: median of threepivot: random pivotMerge sortalready sorted input, n from 64 to 4,096one frame charged as one slot

The stack nobody counts

Merge sort makes 8,192 calls to sort 4,096 elements and holds fourteen of them at once. Depth-first search on a grid holds twelve vertices, or sixty-six, or a hundred and forty-four, depending on which of three equally standard implementations is running. The stack is a resource, it is the one that fails hard rather than slowly, and nothing that watches the data can see it.

space · Space with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

The adversary who hides the edge

The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.

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

Two passes or one, and what the second one costs

Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.

graphs · Graph 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph

A list and a block of memory

The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.

graphs · Graph

Named alongside it

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

AdjacencyAdjacency listCost modelCounted primitivePeak and totalQuicksortRecursion depthTraceAdversary argumentAllocatorAuxiliary spaceCache

All concepts