The catalog of primitives

The recurring primitives that algorithms are built from

Two of these kinds answer different questions. Techniques, motifs and transforms are parts. You can point at them in the finished algorithm. Analysis primitives are how you know it works: the master theorem is not inside mergesort, and the entropy bound is not inside Huffman. Compose the parts; apply the analyses to what you built.

56 primitives so far, the ones the published chapters use; the catalog grows with each chapter. 15 are core spine (marked with a star).

Techniques (design moves)

Divide and conquer ⭐

split a problem into smaller independent subproblems, solve each, recombine.

  • Anchor: sorting a big stack of papers by splitting it in half, sorting each half, then merging
  • Cost: set by the master theorem: O(log n) when only one half is kept (binary search), O(n log n) when both halves are solved and merged in linear time (mergesort)
  • Assumes: subproblems are independent and combinable, and each is a fixed fraction of the whole (a half, a third), not just a few items smaller
  • When it does not hold: a split that peels off only a few items, or a costly merge, kills the speedup; subproblems that overlap get solved again and again (dynamic programming keeps their answers)
  • Transfers to: mergesort, FFT, closest pair of points
  • Recurs in: Contracts and cost models, Geometry and high-dimensional search

Dynamic programming ⭐

cache solutions to overlapping subproblems built on optimal substructure.

  • Anchor: counting routes across a grid where each cell adds the ones above and to its left
  • Cost: number of states times the transition cost
  • Assumes: optimal substructure and overlapping subproblems both hold
  • When it does not hold: the state space blows up, or there is no optimal substructure
  • Transfers to: edit distance, knapsack, Bellman-Ford, Viterbi
  • Recurs in: Paths, trees, routing

Greedy-exchange ⭐

take the locally best choice and never undo it; an exchange argument proves the result is optimal.

  • Anchor: booking the most meetings into one room by always taking the one that ends first among those that still fit
  • Cost: usually near-linear after an initial sort
  • Assumes: an exchange argument works: any best solution can be turned, one swap at a time, into the greedy one without getting worse; a matroid guarantees this, and so do some problems that are not matroids, such as booking meetings
  • When it does not hold: greedy can then be wrong with no warning: with coins of 1, 3 and 4, always taking the largest coin pays 6 as 4+1+1, three coins, where 3+3 needs two
  • Transfers to: Kruskal MST, Huffman coding, making change in euro coins, where largest-first is optimal
  • Recurs in: Paths, trees, routing

Primal-dual ⭐

solve a problem and its dual together; the dual gives a price and a certificate of optimality.

  • Anchor: a market where prices certify that an allocation cannot be improved
  • Cost: problem dependent
  • Assumes: strong duality holds, or the gap is bounded
  • When it does not hold: a duality gap appears when the structure is missing
  • Transfers to: max-flow min-cut, LP duality, primal-dual approximation
  • Recurs in: Flow, cuts, matching

Randomization ⭐

make a random choice to dodge worst-case inputs or to gain concentration.

  • Anchor: shuffling a deck before dealing so no arrangement can be adversarial
  • Keeps true: no input is bad in itself: every input meets the same expected-cost bound, and only the luck of the draw varies
  • Cost: an expected cost instead of a worst case, or a small chance of a wrong answer
  • Assumes: the inputs are not chosen with knowledge of the random choices, and expected or high-probability bounds are acceptable
  • When it does not hold: the worst case is still possible, only unlikely; revealing the random choices can let a caller build bad inputs
  • Transfers to: quicksort pivot, hashing, treaps
  • Recurs in: Geometry and high-dimensional search, Strings

Reduction ⭐

transform a new problem into one that is already solved.

  • Anchor: solving a maze by turning it into a graph and running a known path finder
  • Cost: reduction cost plus the target solver
  • Assumes: the reduction preserves the answer and is cheap
  • When it does not hold: the reduction cost or lost structure dominates
  • Transfers to: matching to flow, LCA to RMQ, NP-hardness, which runs the other way: a known hard problem reduced to the new one proves the new one hard
  • Recurs in: Flow, cuts, matching, Graph structure and decomposition, Paths, trees, routing

A* / admissible heuristic

guide search with a lower-bound estimate and stay optimal if the estimate never overshoots.

  • Anchor: driving toward a city using straight-line distance as a hint about which road to try first
  • Cost: depends on the estimate: a close one can open far fewer nodes than Dijkstra, h = 0 is Dijkstra itself, so the worst case is no better
  • Assumes: the estimate never overshoots the true remaining cost (admissible); a search that never reopens a finished node also needs it consistent: along any edge, the estimate drops by no more than that edge’s length
  • When it does not hold: an inadmissible heuristic loses optimality
  • Transfers to: informed pathfinding, IDA*, branch and bound
  • Recurs in: Paths, trees, routing

Augmentation

repeatedly improve a solution along an augmenting structure until none remains.

  • Anchor: rerouting water through spare pipes until no unused path remains
  • Cost: number of augmentations times the per-step cost
  • Assumes: an augmenting step exists whenever the solution is suboptimal
  • When it does not hold: if some solution short of the best has no augmenting step, the method stops there (flow pushed without undo edges does this); with capacities that are not whole numbers or fractions, badly chosen paths can shrink forever without reaching the maximum; always taking a shortest path (Edmonds-Karp) finishes
  • Transfers to: augmenting paths in flow, bipartite matching, simplex pivots
  • Recurs in: Flow, cuts, matching

Bound and prune

keep the best answer found so far and discard whole branches whose optimistic estimate cannot beat it.

  • Anchor: flat-hunting on a budget: once you have a good one at a price, you stop even viewing the streets where nothing goes for less
  • Cost: worst case unchanged; the whole gain is in branches never explored
  • Assumes: the estimate never understates how good a branch could turn out (it is optimistic), so pruning can never discard the optimum
  • When it does not hold: an estimate that understates prunes the answer away, with no warning; one that is safe but far too optimistic prunes almost nothing, and the search stays exhaustive
  • Transfers to: branch and bound, alpha-beta pruning, knapsack with an LP bound
  • Recurs in: Geometry and high-dimensional search, Paths, trees, routing

Deferred / batched work

postpone work and do it in bulk later, so one fixed setup cost is shared by many items.

  • Anchor: nobody runs the washing machine for one dirty sock; the basket fills and one cycle does the lot
  • Cost: amortized O(1) per item when a batch of k items costs a fixed setup plus O(k)
  • Assumes: the fixed cost of running a batch is large next to the per-item cost, and delay is acceptable
  • When it does not hold: a request arriving before the batch runs still pays for the whole backlog, so worst-case latency grows even as the average falls
  • Transfers to: LSM compaction, buffered I/O, geometric array growth
  • Recurs in: Search

Doubling / geometric growth

grow or probe by powers of two to amortize cost or to find an unknown bound.

  • Anchor: a growing guest list where you buy a table twice as big only when the current one fills
  • Cost: depends on the use: an append to a growing array is amortized O(1); finding an unknown bound d takes O(log d) probes; prefix doubling takes at most ⌈log₂ n⌉ rounds of about n work each
  • Assumes: each step reaches twice as far as the one before, so about log₂ n steps reach any size n; when the work doubles too (copying an array), the last step costs about as much as all the earlier ones together
  • When it does not hold: wasted space up to a factor of two
  • Transfers to: dynamic array, exponential search, binary lifting
  • Recurs in: Search, Strings

Fingerprinting

hash a big object to a short random fingerprint so equality is cheap to test.

  • Anchor: comparing two long documents by their checksums instead of line by line
  • Keeps true: equal objects always get equal fingerprints; unequal ones only usually differ
  • Cost: O(1) comparison after hashing
  • Assumes: the hash has a low collision probability
  • When it does not hold: a false match on a collision
  • Transfers to: Rabin-Karp, Schwartz-Zippel, Bloom filter
  • Recurs in: Strings

Let a read rewrite what it walked

a query that walks a path may rewrite that path as it goes, so the work it had to do anyway makes every later query along it shorter.

  • Anchor: you pull a folder from the middle of a filing drawer and drop it at the front on the way back, so the next time you need it, it is already there
  • Cost: amortized over a sequence, not per operation: a single query can still be long, and the bound says nothing about it
  • Assumes: the rewrite keeps what the structure means, costs no more than the walk it rides on, and is a rule with its own proof that it pays off over every sequence, as splaying, path halving and move-to-front have
  • When it does not hold: reads now change the structure, so sharing it between threads needs coordination, and keeping old versions needs copying or another way to preserve them; a rule without that proof can leave every read slow: in a search tree that rotates each found key up to the root one step at a time, reading every key in order, over and over, costs about n/2 steps a read
  • Transfers to: path halving in union-find, splay trees, move-to-front lists
  • Recurs in: Graph structure and decomposition, Search

Merge the smaller into the larger

when combining two structures, always absorb the smaller one into the larger, so whatever moves lands in a set at least twice the size it was in.

  • Anchor: two supermarket queues combine: you send the three people from the short one over to the long one, not the twenty from the long one to the short
  • Cost: any one element moves at most log n times, because the set holding it doubles every time it moves
  • Assumes: you can cheaply tell which side is smaller, and a merge costs roughly the side that moves rather than both
  • When it does not hold: merge the wrong way round and depth grows linearly instead of logarithmically; the rule only repays the size or rank you have to store when merges are frequent
  • Transfers to: union by rank in union-find, small-to-large merging on trees, mergeable heaps
  • Recurs in: Graph structure and decomposition

Monotone fixed point

repeat a step that only ever moves each value one way, and stop when a full pass changes nothing.

  • Anchor: a rumour spreading through a town: nobody ever un-hears it, so once a day passes with no one new knowing, it has reached everyone it will
  • Cost: termination follows from well-foundedness alone; an iteration count needs a rank with a minimum improvement per step, such as integer weights
  • Assumes: every update moves values in a single direction, and the order they move in is well-founded, so no infinite descending chain of improvements exists
  • When it does not hold: a non-monotone update can oscillate forever; a merely bounded domain is not enough, since values can improve infinitely without ever settling, and a negative cycle in shortest paths is exactly that failure
  • Transfers to: Bellman-Ford relaxation, dataflow analysis, Floyd-Warshall closure
  • Recurs in: Graph structure and decomposition, Paths, trees, routing

Sample, then walk

keep only some checkpoints and recover everything left out by walking to the nearest one.

  • Anchor: a long book with a page number printed only on every tenth page: to find a page’s number, flip back to the nearest numbered page and count the pages you flipped
  • Keeps true: every place is fewer than s steps of walk from a checkpoint, s the spacing
  • Cost: keeping every s-th position of the text stores about n/s checkpoints and costs fewer than s steps of walk per answer, on top of the index the walk runs on
  • Assumes: each step of the walk keeps enough to rebuild the answer, and the way the checkpoints are spaced bounds how long a walk can get
  • When it does not hold: space the checkpoints along the wrong order (every s-th row of the sorted table instead of every s-th position of the text) and a walk can get long; sparse checkpoints make each answer slower
  • Transfers to: checkpoints in a video file, the index of a long log
  • Recurs in: Strings

Spread the work out

take a cost that paying in installments only averages, and pay it in small scheduled pieces so no single operation carries it.

  • Anchor: a monthly bill spread over the month is an average; a standing order that moves a little money every day is what keeps any one day from being hit
  • Cost: a worst-case bound per operation, usually a constant factor more total work than the amortized version
  • Assumes: the big job can be split into pieces that run between operations, and the structure stays correct while the job is half done
  • When it does not hold: the pieces fall behind the arrivals, the backlog grows, and the spike comes back as a stall
  • Transfers to: incremental rehashing of a hash table, background LSM compaction, real-time queues built from two stacks
  • Recurs in: Search

Thinning

when keeping one best partial candidate is unsafe and keeping them all is too many, keep exactly those no other candidate dominates.

  • Anchor: packing for a trip, you discard any option that is both heavier and covers less than one you already have, but you keep the lighter-but-colder one, because it might still win
  • Cost: one dominance pass per step; the entire win is in how small the surviving frontier stays
  • Assumes: candidates are compared by a preorder that is reflexive and transitive but not total, and the undominated set stays small where the full set is exponential
  • When it does not hold: if the order is total, thinning collapses to greedy and greedy was the simpler choice; if nothing dominates anything, the surviving set stays exponential and this is exhaustive search carrying extra bookkeeping
  • Transfers to: Pareto frontier maintenance, knapsack by discarding dominated states, paragraph breaking in TeX
  • Recurs in: Paths, trees, routing

Topological order

linearize a DAG in dependency order so each item comes after its prerequisites.

  • Anchor: getting dressed in an order where socks come before shoes
  • Cost: O(V + E)
  • Assumes: the graph is acyclic
  • When it does not hold: a cycle means no valid order exists
  • Transfers to: build systems, course scheduling, DP over a DAG, k-core peeling (the same removal loop)
  • Recurs in: Graph structure and decomposition

Which side? (orientation / sign test)

answer one geometric question with the sign of a single number: is this point left or right of the line, above or below the plane.

  • Anchor: standing on a road and asking whether a shop is on your left or your right
  • Cost: a few multiplications in the plane; O(d) as a dot product when the plane is given by its normal (SimHash), O(d^3) as a determinant when it is given by d points
  • Assumes: the sign is computed exactly, or by a fast filter that hands the near-zero cases to exact arithmetic
  • When it does not hold: floating-point rounding flips the sign for nearly collinear points and the algorithm built on it breaks
  • Transfers to: SimHash bit (random hyperplane), perceptron / linear classifier, point in polygon (ray crossing) in maps and graphics
  • Recurs in: Geometry and high-dimensional search

Structural motifs

Recursive spatial partition ⭐

split space itself, not just data, into nested regions.

  • Anchor: finding a house on a map by zooming into quadrants
  • Cost: there is no logarithmic worst case: in a balanced 2-D k-d tree a rectangle query visits about sqrt(n) regions plus the k points it reports, and a nearest-neighbor query can visit all n; a 2-D range tree answers in O(log^2 n + k)
  • Assumes: the points really spread in only a few directions (their real dimension is low), so a query can prune many regions, how many depending on the data and the query
  • When it does not hold: the curse of dimensionality: regions end up covering everything
  • Transfers to: k-d tree, quadtree, range tree
  • Recurs in: Geometry and high-dimensional search

Slack in the levels below ⭐

a hierarchy always has room a level down, so inserts do not shove neighbors.

  • Anchor: inserting a name into a sorted paper list shoves everyone right; a filing tree has a free slot below
  • Keeps true: there is always an empty spot below to hang a new key (a binary tree with n nodes has n + 1 of them), so an insert stays on one path down and never shoves the whole row along
  • Cost: O(log n) search and insert when balanced
  • Assumes: following a link one level down is cheap, about one step in memory
  • When it does not hold: when a step down costs a slow fetch (a disk page, a cache miss), every level costs one, and a tall tree is slow; with nothing keeping it balanced, keys that arrive in sorted order grow one long path
  • Transfers to: B-tree pages on disk, binary heap as array, segment-tree ranges
  • Recurs in: Search, Strings

Keep it in layers

stratify items into levels by position or coin flips to get shortcuts.

  • Anchor: express and local subway lines: the express skips ahead over many stops
  • Cost: about log n levels; with random levels a search takes O(log n) steps, expected
  • Assumes: the level distribution is well behaved
  • When it does not hold: random levels give expected and high-probability bounds, never a worst case; levels set by size work only while merging keeps up with the arrivals
  • Transfers to: skip list, LSM tree, the layers of a navigable graph (HNSW)
  • Recurs in: Search

Persistence / path-copying

keep old versions cheaply by copying only the changed path.

  • Anchor: git saves a new version by writing only the changed files and the folders above them; every unchanged file and folder is shared with the old version
  • Cost: O(log n) extra per update
  • Assumes: sharing unchanged structure is safe (immutability)
  • When it does not hold: extra memory per version
  • Transfers to: persistent trees, undo history, copy-on-write
  • Recurs in: Search

Prefix / monoid aggregation

precompute combinable prefixes so range queries are cheap.

  • Anchor: a running total on a receipt lets you get any span by subtracting two points
  • Cost: O(1) to O(log n) per query
  • Assumes: combining is associative: grouping the pieces differently gives the same result; getting a span from two prefixes also needs a way to undo a combine, as subtraction undoes addition
  • When it does not hold: a combine that is not associative breaks it; max and min cannot be undone, so two prefixes do not give a span, and a sparse table (two overlapping blocks, which max and min do not mind) or a segment tree answers instead
  • Transfers to: prefix sums, Fenwick tree, sparse table
  • Recurs in: Search, Strings

Residual / reversible state

keep undo edges so a wrong commitment can be reversed later.

  • Anchor: keeping a receipt so a purchase can be returned
  • Cost: a constant extra per edge
  • Assumes: reversal is well defined
  • When it does not hold: bookkeeping overhead
  • Transfers to: residual graph in flow, backtracking, undo logs
  • Recurs in: Flow, cuts, matching

Succinct / implicit representation

store structure implicitly in bits or arrays, near the information-theoretic minimum.

  • Anchor: a heap stored as a plain array with no pointers at all
  • Cost: near-optimal space with small query overhead
  • Assumes: rank and select, or index arithmetic, are available
  • When it does not hold: the query and update tradeoff tightens
  • Transfers to: heap as array, FM-index, bitvector rank/select
  • Recurs in: Strings

Work in blocks

group items into blocks of a chosen size; inside a block is cheap, crossing to the next block is one step.

  • Anchor: a library shelved into labeled sections you scan within
  • Keeps true: block sizes stay within a fixed ratio, and every leaf sits at the same depth counted in blocks
  • Cost: about log n to the base b+1 blocks deep (b the smallest block size), times what one block costs to cross
  • Assumes: looking inside a block is cheap compared with crossing to the next one
  • When it does not hold: blocks too small and it is a plain tree again; blocks too uneven and the depth grows
  • Transfers to: the red-black tree’s one-or-two-key nodes, B-tree pages, sqrt(n) blocks over an array
  • Recurs in: Search, Strings

Invariants and certificates

Cut certifies flow ⭐

a matching bound proves optimality: no flow can exceed any cut, so a flow as large as some cut is a maximum flow, and that cut is a minimum cut.

  • Anchor: the narrowest bottleneck on a road proves the maximum traffic that can pass
  • Cost: found alongside the primal solution
  • Assumes: the min-max duality holds for the structure
  • When it does not hold: no witness exists when duality fails
  • Transfers to: max-flow min-cut, Konig theorem, LP duality
  • Recurs in: Flow, cuts, matching

Keep an invariant ⭐

choose one property and keep it true after every step, whether the step is a loop’s pass or an operation on a structure; a loop invariant is the loop’s case, and it proves the answer correct.

  • Anchor: keeping your place with a bookmark that always marks exactly what you have read
  • Keeps true: the chosen property: true before the first step and true again after every step
  • Cost: a reasoning tool
  • Assumes: each step can be shown to keep the property, and the property, where the work ends, says the answer is right
  • When it does not hold: a step that does not keep the property (an off-by-one at a boundary is the usual one), or a property too weak to say the answer is right when the work ends
  • Transfers to: binary search bounds, Dijkstra settled set, insertion-sort prefix, the sorted order a search tree keeps
  • Recurs in: Contracts and cost models, Paths, trees, routing

Carry what you know

when a step needs a value the invariant does not supply, introduce a variable to hold it and add a conjunct saying what it holds, then repair it each step instead of recomputing it.

  • Anchor: a shopkeeper keeps a running total on the till rather than adding the whole basket again after each item goes in
  • Cost: one extra update per step, in exchange for removing a recomputation from that step
  • Assumes: the extra quantity is cheaper to repair after a step than to recompute from scratch, and the repair itself needs only what is already at hand
  • When it does not hold: every variable added is one more thing each step must restore; strengthen too far and the loop body grows faster than the recomputation it saved
  • Transfers to: a running sum beside a sliding window, cached subtree sizes for rank queries, Dijkstra’s taking the relation outside
  • Recurs in: Contracts and cost models, Search

Invariant from both ends

when a loop modifies its own input, the invariant must say what is already done and what is still untouched: the first half is a weakening of the postcondition, the second comes from the precondition.

  • Anchor: repainting a fence plank by plank: the useful thought is not “these are green” but “these are green and the rest are still the old color”, which is what tells you where to pick up
  • Cost: each step must restore both halves, so the boundary between done and untouched is where all the work happens
  • Assumes: precondition and postcondition can be put in the same form, so the invariant reads as a generalization of both rather than as two unrelated clauses
  • When it does not hold: weakening only the postcondition leaves the untouched part unconstrained, so nothing stops a step from corrupting what the loop has not reached yet, and the error stays invisible until some step reads ahead
  • Transfers to: in-place array reversal, the partition loop in quicksort, insertion sort’s sorted prefix and untouched suffix
  • Recurs in: Contracts and cost models, Search

Matroid

the structure on which greedy finds a best-weight set for every choice of weights.

  • Anchor: picking a set of roads where no chosen road closes a loop
  • Cost: a structural reasoning tool
  • Assumes: the independence system satisfies the exchange axiom
  • When it does not hold: not a matroid means some weights make greedy fail, though greedy can still win on a particular problem, as earliest-finish scheduling does
  • Transfers to: MST greedy, scheduling unit jobs with deadlines, linear independence
  • Recurs in: Paths, trees, routing

Monovariant / progress measure

a quantity that strictly changes one way proves the process halts.

  • Anchor: a countdown timer that only ticks down must reach zero
  • Cost: a reasoning tool
  • Assumes: the quantity is a whole number (or moves by at least a fixed amount each step) and cannot pass a limit
  • When it does not hold: a quantity that can move by ever smaller amounts may never reach its limit: 1, 1/2, 1/4, … falls forever
  • Transfers to: flow value with whole-number capacities, Euclid gcd, elimination rounds
  • Recurs in: Contracts and cost models

Potential function

track a bounded energy that bounds amortized cost or proves termination.

  • Anchor: a savings account where cheap operations deposit and expensive ones withdraw
  • Cost: an analysis tool with no runtime cost
  • Assumes: for amortized costs, the potential starts at zero and never goes negative, so the amortized costs add up to at least the real ones
  • When it does not hold: finding the right potential is hard
  • Transfers to: union-find, splay trees, simplex anti-cycling
  • Recurs in: Graph structure and decomposition

Replace a constant by a variable

turn a fixed quantity in the goal into a variable, and the goal becomes an invariant you can hold while the variable moves toward its fixed value.

  • Anchor: you cannot spot the tallest person in a crowd at a glance, so you carry the tallest so far; when the crowd runs out, the running answer is the answer
  • Cost: each step costs whatever restores the relation; the number of steps is the distance the variable must travel to reach its fixed value
  • Assumes: weakening one quantity in the goal leaves a relation that is easy to establish at the start and cheap to restore after each step
  • When it does not hold: a carelessly chosen generalization is harder to maintain than the original goal; Dijkstra’s warning is that the wider class must be chosen deliberately, since not every generalization helps
  • Transfers to: the shrinking interval in binary search, the settled set in Dijkstra’s algorithm, the sorted prefix in insertion sort
  • Recurs in: Contracts and cost models, Search

Shrink without moving the answer

take a step that provably leaves the answer unchanged while making the problem smaller, and repeat until the remainder is small enough to read off.

  • Anchor: looking a word up in a paper dictionary: you open the middle, decide which half it is in, and the word you want is still somewhere in the half you kept
  • Cost: set by how fast the problem shrinks: subtracting a constant gives linear, halving gives logarithmic
  • Assumes: some step strictly reduces the problem and is proved not to change the answer, so the answer to what remains equals the answer to what you started with
  • When it does not hold: a step that shifts the answer even slightly makes the whole walk wrong, and nothing shows it until the base case returns a plausible wrong value
  • Transfers to: Euclid’s gcd, binary search, Kaldewaij’s tail invariant F.x.y = F.A.B
  • Recurs in: Contracts and cost models, Search

Take a conjunct as the invariant

split the goal into conjuncts, hold one of them true throughout, and let the negation of the other be the loop guard, so the loop can only stop where both hold.

  • Anchor: walking a street for a door number: keep “I have not passed it” true the whole way, and keep walking while “this is not it” – when you stop, both are true and you are standing at it
  • Cost: the number of steps is the distance the guard must travel; each step costs whatever restores the held conjunct
  • Assumes: the goal is a conjunction, one conjunct is cheap to establish at the start, and steps exist that drive the other toward true without breaking the first
  • When it does not hold: the held conjunct alone may not make the bound function decrease, and the invariant then has to be strengthened before termination goes through – Kaldewaij’s integer square root needs 0 <= x added for exactly this reason
  • Transfers to: integer square root by increment, the loop bounds in binary search, the partition loop in quicksort
  • Recurs in: Contracts and cost models, Search

Analysis tricks

Adversary / decision-tree lower bound ⭐

an adversary or decision tree forces an information-theoretic minimum number of steps.

  • Anchor: twenty questions needs about log2(N) yes or no questions to pin one item
  • Cost: a reasoning tool
  • Assumes: the model counts the right operations, for example comparisons
  • When it does not hold: the bound covers only what its model counts: radix sort is not a comparison sort, so it can beat n log2 n
  • Transfers to: comparison-sort lower bound, ball weighing, searching
  • Recurs in: Contracts and cost models

Concentration (Markov to Chernoff) ⭐

a sum of many small independent terms hugs its mean tightly.

  • Anchor: flip a thousand coins and the count of heads is almost surely near five hundred
  • Cost: a reasoning tool
  • Assumes: Markov needs only a value that is never negative; Chebyshev needs the variance (for a sum, pieces independent in pairs are enough); Chernoff needs independent pieces of bounded size; a result of independent inputs, none of which can move it much (bounded differences), concentrates too
  • When it does not hold: heavy tails or dependence break it
  • Transfers to: sketch error, sampling error, randomized rounding
  • Recurs in: Geometry and high-dimensional search

Master theorem ⭐

solve divide-and-conquer recurrences by comparing work at the root versus the leaves.

  • Anchor: a rumor splitting to two people each round: count total tellings level by level
  • Cost: a reasoning tool
  • Assumes: subproblems of equal size and polynomial work
  • When it does not hold: uneven splits fall outside the theorem
  • Transfers to: mergesort, binary search, Strassen
  • Recurs in: Contracts and cost models

Pay in installments ⭐

charge cost over a sequence so rare expensive operations average out (amortization).

  • Anchor: a monthly subscription spreads one big cost over many days
  • Keeps true: the work saved up always covers the next expensive operation
  • Cost: an amortized bound per operation
  • Assumes: operations run one after another from a known start, each on the state the last one left, and the bound is proved for every such sequence, not only typical ones
  • When it does not hold: if the design lets the expensive step come right back, it is paid every time (an array that doubles when full and halves when half full, with push and pop alternating at the edge); going back to an old state can spend the same savings twice; and one operation can still be slow
  • Transfers to: dynamic array, union-find, B-tree splits
  • Recurs in: Contracts and cost models, Geometry and high-dimensional search, Graph structure and decomposition, Search, Strings

Union bound ⭐

the chance any bad event happens is at most the sum of their chances.

  • Anchor: the chance any of ten fragile items breaks is at most ten times one breaking
  • Cost: a reasoning tool
  • Assumes: works even under dependence, no independence needed
  • When it does not hold: loose when the events overlap heavily
  • Transfers to: hashing collisions, skip list w.h.p., Johnson-Lindenstrauss
  • Recurs in: Geometry and high-dimensional search, Search

Entropy / information bound

entropy sets the floor on how few bits can encode data, and a decision-tree lower bound.

  • Anchor: a fair coin needs one bit per flip while a biased coin needs less
  • Cost: a reasoning tool
  • Assumes: a source model or a comparison model
  • When it does not hold: beating the floor is impossible, so a claim below it is simply wrong
  • Transfers to: Huffman optimality, compression floor, sorting lower bound
  • Recurs in: Contracts and cost models

Exchange argument

swap any solution toward a canonical one without loss to prove greedy is optimal.

  • Anchor: reordering a playlist by swaps to show a chosen order is best
  • Cost: a reasoning tool
  • Assumes: swaps never worsen the objective
  • When it does not hold: a swap that hurts breaks the proof
  • Transfers to: MST optimality, scheduling proofs, Huffman
  • Recurs in: Paths, trees, routing

Linearity of expectation

the expected total is the sum of expected parts, even when the parts depend.

  • Anchor: the expected number of people sharing your birthday is just the sum over each person
  • Cost: a reasoning tool
  • Assumes: finite expectations, nothing more
  • When it does not hold: misused for variance, which is not linear
  • Transfers to: quicksort comparisons, hashing load, coupon collector
  • Recurs in: Geometry and high-dimensional search

Transforms

Burrows–Wheeler transform

permute text to cluster equal contexts, making it both compressible and searchable.

  • Anchor: write out every rotation of a quote, sort them, and read off the last letters: repeated letters bunch together
  • Keeps true: it can be undone when the text ends in a marker ($) that appears exactly once and is the smallest letter: equal letters keep their order, so the text can be rebuilt
  • Cost: O(n) with suffix structures
  • Assumes: the data has repeated contexts
  • When it does not hold: random data gains nothing
  • Transfers to: bzip2, FM-index, compressed search
  • Recurs in: Strings

Canonical form

rewrite every object into one standard representative, so asking whether two are equivalent becomes asking whether they are identical.

  • Anchor: two guest lists with the same names in a different order look different until you alphabetise both
  • Keeps true: every object has exactly one standard form, and equivalent objects share it
  • Cost: one normalization per object; equality is then a structural comparison of the forms, dropping to pointer identity only if they are interned
  • Assumes: computing the standard form costs less than comparing directly
  • When it does not hold: if two equivalent objects can normalize differently, equality silently reports false; if normalizing is expensive, the comparison it replaced was the cheaper one
  • Transfers to: sorting before deduplication, hash-consing, normalizing a fraction to lowest terms
  • Recurs in: Strings

Contraction / minor

shrink the structure while preserving the property of interest.

  • Anchor: folding a road map so two towns merge, simplifying the routes
  • Cost: problem dependent
  • Assumes: the contraction keeps the target invariant
  • When it does not hold: contracting the wrong part loses the answer
  • Transfers to: Karger min-cut, Boruvka MST, shrinking blossoms in matching
  • Recurs in: Graph structure and decomposition

Euler-tour / linearize tree

flatten a tree to an array so range primitives apply to subtrees.

  • Anchor: reading a family tree top to bottom into a single ordered list
  • Cost: O(n) to build
  • Assumes: a rooted tree
  • When it does not hold: updates that change shape need care
  • Transfers to: subtree queries, LCA to RMQ, heavy paths
  • Recurs in: Graph structure and decomposition

Make the state remember it

when the best next step depends on something the state does not record, make it part of the state: one copy of each state per value it can take.

  • Anchor: a street corner with a full battery and the same corner with an empty one are different places to plan from
  • Cost: the old vertices times the number of values
  • Assumes: the added quantity takes few values, or can be cut into few levels without changing the answer
  • When it does not hold: the graph grows by the number of values, and a quantity with many values makes it too big to search
  • Transfers to: Bellman-Ford’s rounds, where the variable is the number of arrows used, knapsack, where it is the capacity used, hybrid A* for parking a car, where it is the heading
  • Recurs in: Paths, trees, routing

Random projection (JL)

project to far fewer random dimensions while nearly preserving distances.

  • Anchor: one photo of a sculpture can hide a point behind another, but enough photos from random angles, taken together, keep every distance between its points nearly in proportion, very likely
  • Cost: O(n d k) to project
  • Assumes: target dimension about log(n)/eps^2
  • When it does not hold: too few dimensions distort the distances
  • Transfers to: Johnson-Lindenstrauss, LSH, sketching
  • Recurs in: Geometry and high-dimensional search

Random-hyperplane rounding

round a vector relaxation by cutting with a random hyperplane.

  • Anchor: splitting a seated friend group in two with a random line drawn across the table
  • Cost: an SDP solve plus a random cut
  • Assumes: an SDP vector solution exists
  • When it does not hold: the ratio is limited by the relaxation
  • Transfers to: Goemans-Williamson Max-Cut, SDP rounding, correlation clustering

Showcase compositions

Famous algorithms are compositions of primitives, not catalog entries.

Algorithm Built from Idea
A* search A* / admissible heuristic + Search with a to-do list Dijkstra steered by a consistent lower bound on the cost still to go; with a zero estimate it is Dijkstra
B-tree Slack in the levels below + Work in blocks tree-slack plus block decomposition tuned for I/O
Ball weighing Divide and conquer ternary decision tree finds the odd ball in the fewest weighings
Bellman-Ford Dynamic programming + Make the state remember it dynamic programming over the number of arrows used, which tolerates negative arrows; one more round that still lowers a cost reports a negative cycle
Bipartite matching Augmentation + Reduction reduction to flow plus augmenting paths
Bitvector rank/select Succinct / implicit representation + Work in blocks two-level superblock+block counting index; the strings chapter builds it, and wavelet trees and LOUDS build on it
Bridges, cut vertices and the block-cut forest Contraction / minor + DFS timestamps / low-link one depth-first walk with low-link numbers finds every link and vertex whose failure alone splits the network; contraction turns each block into one node, so the forest says which cut vertices separate two places
Convex hull (Andrew’s monotone chain) Which side? (orientation / sign test) sort the points, then sweep left to right and back keeping only strict left turns (the which-side test); each point pushed once and popped at most once, so O(n log n), the sort
Dijkstra Keep an invariant + Search with a to-do list best-first search with a kept invariant: a settled vertex’s cost is final; needs no negative arrow
Edmonds-Karp Augmentation + Residual / reversible state augmentation over a residual graph, BFS chosen paths
Eulerization (Chinese Postman) Reduction + repeat roads until every place has an even number of them naive duplication versus smart min-weight matching: same brick, dumb vs smart
FM-index Burrows–Wheeler transform + Sample, then walk + Succinct / implicit representation + Work in blocks BWT plus rank and select for search in compressed space; positions kept at every s-th place of the text say where each match starts
Graph index for approximate nearest neighbor (HNSW) Keep it in layers + Navigable neighbor graph + Search with a to-do list a few diverse neighbors per place (RNG-style pruning) and a best-first beam walk; HNSW adds layers that act as highways
LCP array Carry what you know for each suffix, the letters it shares with the one sorted before it; the count is carried from one text position to the next and drops by at most one, so the whole pass is linear (Kasai)
Locality-sensitive hashing Fingerprinting + Random projection (JL) + Recursive spatial partition + Which side? (orientation / sign test) SimHash: a random cut through the origin gives one bit (the hull’s which-side test again), bits make a key, several tables, every candidate measured exactly
Minimum spanning tree Greedy-exchange greedy-exchange, and the matroid of loop-free road sets is why it works for any weights; to check a finished tree, every edge left out weighs at least as much as each tree edge on the loop it would close
Patricia / radix tree Canonical form + Slack in the levels below trie with single-child chains collapsed into labeled edges
Rabin-Karp Fingerprinting + Randomization fingerprinting with a rolling random hash
Range tree Divide and conquer + Prefix / monoid aggregation + Recursive spatial partition a 1-D query splits at one node and walks two paths down; the answer is a few whole subtrees
Suffix array Divide and conquer + Doubling / geometric growth + a position, not a copy sorted suffix positions; built by prefix doubling with a radix sort per round, searched by binary search
Tarjan SCC Contraction / minor + DFS timestamps / low-link one depth-first walk with low-link numbers finds the groups that can all reach each other; contraction shrinks each group to one vertex, leaving a graph of groups with no cycle
Trie the word is the path R-way prefix tree; the key is the path, so no node stores a character
Union-Find Let a read rewrite what it walked + Merge the smaller into the larger merge the smaller tree into the larger, and let each find flatten the path it walked; the inverse-Ackermann bound is what the two together buy
k-d tree Bound and prune + Recursive spatial partition + Search with a to-do list split space by alternating axes; nearest neighbor by bound-and-prune with a best-first queue

An idea in italics is a part of that structure that is not catalogued as a primitive.