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

Divide and conquer — where it appears

Splitting a problem into independent parts, solving each and combining, which turns a repeated recomputation into a geometric series rather than a product. The combine step is where its cost actually lives, and a method whose combine is linear and whose split is even is the shape every good bound here has.

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

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 —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held

The alignment that fits in one line

Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.

space · Distance cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells

The split scan cut into blocks

Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.

tables · Table

Named alongside it

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

CacheDynamic programmingLocalityRecursionWorking setAccess patternAlignmentAuxiliary spaceCache obliviousCall stackComparison countEdit distance

All concepts