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.

24 primitives so far, the ones the published chapters use; the catalog grows with each chapter. 8 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
Assumption: subproblems are independent and combinable, split is balanced
Fails when: an unbalanced split or a costly merge kills the speedup
Cost: often O(n log n) via the master theorem
Transfers to: mergesort, FFT, closest pair of points

Recurs in: Contracts and cost models

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
Assumption: randomness is available and expected or high-probability bounds are acceptable
Fails when: the worst case is still possible, only unlikely
Cost: expected cost rather than worst case
Transfers to: quicksort pivot, hashing, treaps

Deamortization

take a cost that amortization 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
Assumption: the big job can be split into pieces that run between operations, and the structure stays correct while the job is half done
Fails when: the pieces fall behind the arrivals, the backlog grows, and the spike comes back as a stall
Cost: a worst-case bound per operation, usually a constant factor more total work than the amortized version
Transfers to: incremental rehashing of a hash table, background LSM compaction, real-time queues built from two stacks

Recurs in: Search

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
Assumption: the fixed cost of running a batch is large next to the per-item cost, and delay is acceptable
Fails when: a request arriving before the batch runs still pays for the whole backlog, so worst-case latency grows even as the average falls
Cost: amortized O(1) per item when a batch of k items costs a fixed setup plus O(k)
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
Assumption: geometric growth keeps total work linear
Fails when: wasted space up to a factor of two
Cost: amortized O(1) per operation
Transfers to: dynamic array, exponential search, binary lifting

Recurs in: Search

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
Assumption: the hash has a low collision probability
Fails when: a false match on a collision
Cost: O(1) comparison after hashing
Transfers to: Karp-Rabin, Schwartz-Zippel, Bloom filter

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
Assumption: the rewrite preserves what the structure means, and queries repeat on overlapping paths often enough to repay it
Fails when: reads now mutate, so the structure stops being safe to share between threads or to keep as a persistent version, and a workload that never repeats a path pays the rewrite for nothing
Cost: amortized over a sequence, not per operation: a single query can still be long, and the bound says nothing about it
Transfers to: path halving in union-find, splay trees, move-to-front lists

Recurs in: Search

Structural motifs

Tree = 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
Assumption: the tree stays balanced (depth O(log n))
Fails when: rebalancing cost, plus pointer and cache overhead
Cost: O(log n) search and insert when balanced
Transfers to: B-tree pages on disk, binary heap as array, segment-tree ranges

Recurs in: Search

Block / sqrt-n decomposition

split into blocks of size about sqrt(n), sitting between a flat array and a tree.

Anchor: a library shelved into labeled sections you scan within
Assumption: block size tuned near sqrt(n)
Fails when: worse than a tree for skewed workloads
Cost: O(sqrt n) per operation
Transfers to: sqrt decomposition, block search, B-tree fanout

Recurs in: Search

Layering by rank/probability

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

Anchor: express and local subway lines: the express skips ahead over many stops
Assumption: the level distribution is well behaved
Fails when: expected rather than worst-case guarantees
Cost: O(log n) expected
Transfers to: skip list, LSM tree, BFS layers

Recurs in: Search

Persistence / path-copying

keep old versions cheaply by copying only the changed path.

Anchor: git keeps every version by storing only what changed
Assumption: sharing unchanged structure is safe (immutability)
Fails when: extra memory per version
Cost: O(log n) extra per update
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
Assumption: the combine operation is associative (a monoid)
Fails when: a non-associative combine breaks it
Cost: O(1) to O(log n) per query
Transfers to: prefix sums, Fenwick tree, sparse table

Recurs in: Search

Invariants and certificates

Loop invariant ⭐

a property preserved every iteration proves the algorithm correct.

Anchor: keeping your place with a bookmark that always marks exactly what you have read
Assumption: it holds initially and is maintained each step
Fails when: a subtle off-by-one breaks maintenance
Cost: a reasoning tool
Transfers to: binary search bounds, Dijkstra settled set, insertion-sort prefix

Recurs in: Contracts and cost models

Carry an auxiliary quantity

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
Assumption: 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
Fails when: 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
Cost: one extra update per step, in exchange for removing a recomputation from that step
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
Assumption: 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
Fails when: 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
Cost: each step must restore both halves, so the boundary between done and untouched is where all the work happens
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

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
Assumption: the quantity is bounded
Fails when: no strict change means possible non-termination
Cost: a reasoning tool
Transfers to: increasing flow value, Euclid gcd, elimination rounds

Recurs in: Contracts and cost models

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
Assumption: weakening one quantity in the goal leaves a relation that is easy to establish at the start and cheap to restore after each step
Fails when: 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
Cost: each step costs whatever restores the relation; the number of steps is the distance the variable must travel to reach its fixed value
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
Assumption: 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
Fails when: 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
Cost: set by how fast the problem shrinks: subtracting a constant gives linear, halving gives logarithmic
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
Assumption: 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
Fails when: 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
Cost: the number of steps is the distance the guard must travel; each step costs whatever restores the held conjunct
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
Assumption: the model counts the right operations, for example comparisons
Fails when: the wrong model gives a wrong bound (the old book’s error)
Cost: a reasoning tool
Transfers to: comparison-sort lower bound, ball weighing, searching

Recurs in: Contracts and cost models

Amortization ⭐

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

Anchor: a monthly subscription spreads one big cost over many days
Assumption: expensive operations are rare relative to cheap ones
Fails when: an adversary forces the expensive operation often
Cost: an amortized bound per operation
Transfers to: dynamic array, union-find, B-tree splits

Recurs in: Contracts and cost models, 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
Assumption: subproblems of equal size and polynomial work
Fails when: uneven splits fall outside the theorem
Cost: a reasoning tool
Transfers to: mergesort, binary search, Strassen

Recurs in: Contracts and cost models

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
Assumption: works even under dependence, no independence needed
Fails when: loose when the events overlap heavily
Cost: a reasoning tool
Transfers to: hashing collisions, skip list w.h.p., Johnson-Lindenstrauss

Recurs in: 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
Assumption: a source model or a comparison model
Fails when: beating the floor is impossible, so a claim below it is simply wrong
Cost: a reasoning tool
Transfers to: Huffman optimality, compression floor, sorting lower bound

Recurs in: Contracts and cost models

Showcase compositions

Famous algorithms are compositions of primitives, not catalog entries.

Algorithm	Built from	Idea
B-tree	Block / sqrt-n decomposition, Tree = slack in the levels below	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