Data structures and algorithms, oriented

Reaching a[k] costs the same whether k is 0 or a million, because the address is arithmetic: start of array, plus k times element size. That is what random access means, and every other layout is measured against it.

Binary search is where people first misread a precondition. It is not a faster search, it is a faster search on ordered data, and it is easy to write almost correctly. Suppose lo and hi are both near the top of the integer range: (lo + hi) / 2 overflows, so write lo + ((hi - lo) >> 1). The boundary convention must also match the exit test.

Recursion costs what the source does not show: a stack frame per call. A textbook quicksort over 8,000 already-sorted integers did not merely slow down in testing — it died with a stack-overflow error, because the recursion went n deep instead of log n.

Python's reference is exact about bits: a left shift by n multiplies by pow(2, n), a right shift is floor division by it, and results are computed in two's complement with infinite sign bits.

Rule: before optimizing an algorithm, know what one memory access and one call actually cost.

Big-O is an upper bound on a growth shape, which is why "at least O(n²)" is meaningless — the notation cannot express a floor. It also hides the constant factors, and the input size below which it says nothing.

The misconception worth destroying is that the lower big-O always wins. Measured here on random arrays, microseconds per sort:

Insertion sort is quadratic and won every size to 128 against two merge implementations, which is why production sorts switch to a quadratic sort on short runs. Past the crossing the constants stop mattering: at 100,000 elements binary search beat a linear scan by about 550×.

Amortized analysis contains no probability — it guarantees any k operations cost at most k times the stated figure. Growing an array by one element per overflow makes n appends quadratic; doubling makes them linear. Measured over 40,000 appends: 65,535 element copies in 0.13 ms, against 799,980,000 in 221 ms.

The trap is reading "amortised constant" as "always fast". Two million appends averaged 22.6 ns, but the one at index 1,048,576, where the buffer doubled, took 530 µs — about 23,000× the average.

Rule: quote growth to compare algorithms, measure at your real size to choose one, and never ship against the average when latency counts.

A stack is last-in-first-out, a queue is first-in-first-out, a deque allows both ends — none says how the data is stored. An array indexes in constant time but pays to insert anywhere but the end; a linked list inverts that: cheap to splice at a node you hold, k hops to reach element k.

These costs are documented, not folklore. Python's library states that lists incur O(n) memory movement for pop(0) and insert(0, v), while a deque appends and pops from either side at approximately O(1). The common mistake is reaching for a list as a queue: emptying a 200,000-element list from the front measured 3,484 ms with list.pop(0) against 8 ms with deque.popleft().

But swapping containers reprices other operations: the same page notes deque indexing is O(1) at both ends and O(n) in the middle, and measured, the middle was 199× slower than an end.

One habit is worth understanding rather than memorizing: building a string by repeated s = s + "x". CPython can sometimes extend it in place rather than copying, but only while the string has a single reference — so the same loop stayed linear inside a function here and turned clearly superlinear at module scope. Suppose you cannot tell which you have: build a list and join it once, the form linear everywhere.

Rule: name the operation you perform most, look up its documented cost in the container you use, and confirm it.

Merge sort splits, sorts each half, and merges in one linear pass — the canonical n log n. It is stable, so equal elements keep their order, and pays Θ(n) auxiliary space.

Quicksort partitions around a pivot and recurses in place, but the split is only as good as the pivot. Suppose the array arrives sorted and the pivot is the first element: it is the minimum every time, so one side is always empty and the cost goes quadratic. Measured, 4,000 sorted integers took 31× longer than the same values shuffled, and at 8,000 the run died with a stack overflow — and sorted is what an ORDER BY hands you.

Sorting has a proven floor: distinguishing n! orderings needs a decision tree whose height grows at least like n log n. Counting and radix sorts get under it by indexing on the key's value, at Θ(n + k).

Stability is how you sort by two keys — sort by the secondary, then stably by the primary. On 2a 2b 1c a selection sort returned 1c 2b 2a, equal keys swapped, where a stable sort gave 1c 2a 2b; least-significant-digit radix sorting is wrong without it. A related failure is silent: the comparator (a, b) => a > b yields booleans, never a negative, and left a 26-element array unsorted.

Rule: use the library sort; if you hand-roll one, randomize the pivot and settle stability before speed.

A priority queue is an interface: insert, then remove the extreme. A binary heap implements it in a plain array, because a complete binary tree needs no pointers — the children of index i sit at 2i and 2i+1, the parent at ⌊i/2⌋.

The invariant is only local — every parent is at least as small as its children — and confusing that with sortedness is the classic error. For example, [1, 3, 2, 5, 9, 8, 7] is a valid min-heap and plainly not sorted; the root is the only element you know anything about.

Insertion swims a new item up; removal takes the root, moves the last item there and sinks it. Both walk one root-to-leaf path, so both are O(log n).

Where a heap earns its keep is selection. For the top 10 of a million values, keep a 10-element heap and compare each new value against its weakest. Measured, the full sort took 230 ms and the heap 10 ms — and the heap held ten items, not a million.

Rule: reach for a heap when you repeatedly need the extreme of a changing set, never when you need it in order.

An associative array promises insert, look up and delete; a set is the same with the values discarded. Binary search over a sorted array is logarithmic to read but linear to update, since insertions shift everything after; a search tree makes both logarithmic.

The tree property is local — smaller keys left, larger right — with one lovely consequence: an in-order traversal emits the keys sorted. It also buys what a hash table cannot do: minimum, predecessor, successor, range, rank.

All of those cost the height of the tree, and that is where it betrays you. Suppose the keys arrive in order, as they do from a database or an identifier column: each goes to the far right and the tree becomes a linked list. Measured, inserting 0…99,999 in order gave a height of exactly 100,000, while the same keys shuffled gave 44, against a floor near 16.6. A balanced tree is not a luxury here.

Balanced trees remove the possibility instead of hoping. The bookkeeping varies — rotations, node splitting, color invariants — but the contract is identical: height stays logarithmic whatever the insertion order. B-trees instead use a branching factor that fills a disk block, which is why databases and filesystems use them.

Rule: if you never ask an ordered question a hash table is simpler and faster; if you do use a tree, use a balanced one.

The key space exceeds the table, so collisions are inevitable, not a flaw to engineer away. Chaining hangs a list off each slot at Θ(1 + α), where α is items over slots; open addressing probes onward, at an expected cost bounded by 1/(1 − α).

The misconception is that a lookup is O(1) however full the table is. Measured on one 65,536-slot table with linear probing:

Identical code and table — only the load factor moved, which is why resizing is not optional tuning.

The hash function matters as much as the load. One that mixed badly — a 32-bit multiply silently losing its low bits to floating-point rounding — took the same table at 50% load from 1.49 probes to 81.7; with every key in one slot the average came to exactly n/2.

Two contracts are also on you: equal keys must hash equally, and a key must not change in the table. Measured in Python, mutating one after insertion made it unfindable while the entry sat in the dictionary — though JavaScript's Map keys by identity, so the same mutation is harmless. Hashing also destroys order: over 50,000 keys a set answered membership 107× faster than a sorted array, and 766× slower at "smallest key ≥ x".

Rule: hash when you look items up by exact key, watch the load factor, and switch to a tree when you need a range or a neighbor.

An adjacency matrix stores a cell per possible pair, taking Θ(V²) space; an adjacency list stores each vertex's neighbors, taking Θ(V + E). Real graphs are overwhelmingly sparse, so lists win — a matrix for twenty billion vertices is unstorable, not a tuning choice.

Both searches visit every reachable vertex once, at O(V + E). Breadth-first search uses a queue and expands level by level, reaching each vertex by a path of fewest edges; depth-first search follows one path until stuck and backtracks, which the call stack handles.

The mistake is treating them as interchangeable, because the difference is correctness, not speed. Suppose you need the fewest steps: measured on a seven-vertex ring with a shortcut, breadth-first search returned the one-edge path from 0 to 6 while depth-first search returned a valid six-edge path — both paths, only one shortest. Depth-first recursion depth also equals path length, so on a large graph it overflows the stack.

Direction makes reachability one-way. A directed acyclic graph — directed, no cycles — admits a topological order in which every edge points forward; reversing the order a depth-first search finishes vertices produces one, and failing to is exactly cycle detection. That answers build ordering, task scheduling, and circular-import errors.

Rule: name the vertices and edges before choosing an algorithm, then let the question pick the search — fewest edges means breadth-first search.

A spanning tree touches every vertex without cycles; a minimum one has the least total weight. Greed works because of the cut property: split the vertices any way you like, and the cheapest edge crossing that split is in a minimum spanning tree.

Kruskal's sorts the edges and adds each unless it closes a cycle, so it repeatedly asks "are these two already connected?". Prim's grows one tree, absorbing the cheapest edge leaving it, so it repeatedly asks a priority queue for a minimum — and its cost is dominated by that queue: O(V²) with an array, O(E log V) with a binary heap, so on a dense graph the array wins.

Kruskal's question is answered by union-find, where the gap between implementations is not subtle. For example, over 20,000 vertices and 20,000 random unions, relabeling every element on each merge measured 730 ms and 335 million steps; merging the smaller tree into the larger and flattening paths took 0.43 ms and 20,611 steps.

One confusion is worth naming: a minimum spanning tree is not a shortest-path tree. It minimizes the tree's total weight, not the distance from any starting vertex.

Rule: use a spanning tree to connect everything cheaply, and a shortest-path algorithm for one vertex's distances.

The shared primitive is relaxation: if the estimate for v is worse than the estimate for u plus the weight of the edge from u to v, lower it.

Dijkstra's policy is to repeatedly take the unfinished vertex with the smallest estimate and declare it final. That greedy claim rests entirely on weights being non-negative: once the closest remaining vertex is settled, no detour can improve it, because detours only add.

The failure is quiet, which is what makes it dangerous. Suppose three vertices with edges S→A of weight 1, S→B of weight 2 and B→A of weight −2: measured, Dijkstra finalized A at 1 and never revisited it. The true shortest path is S→B→A at 0, which Bellman-Ford returned correctly. No exception, no warning, just a wrong number.

Bellman-Ford assumes no ordering: it relaxes every edge V−1 times and pays O(VE) for the generality. One extra pass then detects a negative cycle, which makes "shortest path" undefined rather than merely hard. On a directed acyclic graph, relaxing in topological order is one linear pass and tolerates negative weights.

Rule: check the edge weights first — non-negative means Dijkstra, negative means Bellman-Ford, acyclic means neither.

Two properties license it. Optimal substructure means an optimal solution contains optimal solutions to its subproblems; overlapping subproblems means a plain recursion re-solves the same few cases. Divide and conquer has the first without the second.

The size of the win is easy to underrate. For example, naive recursive Fibonacci at n = 35 measured 29,860,703 calls in 86 ms; the identical recursion with a table made 36 distinct calls in 0.002 ms. Thirty million calls concealed thirty-six distinct subproblems.

The real skill is deriving one, not recognizing named problems, and it is mechanical. Write the honest brute-force recursion, see which arguments actually vary — those are your state — then memoise top-down or fill the same table bottom-up. That also gives the cost before you write code: distinct states times work per state.

Greedy claims more: take the locally best option and keep no table. Where it holds it is faster and simpler — scheduling the most intervals by always taking the earliest finisher. Where it does not, it is confidently wrong: best value-per-weight is optimal when you may take fractions and arbitrarily bad when items are indivisible.

Rule: write the brute force first, name the varying arguments as your state, and claim greed only when you can justify it.

Two pointers is the first substitution. Suppose the data is sorted: walking one index in from each end lets a single comparison eliminate a whole row of candidates. Measured, searching 32,000 sorted integers for a pair summing to an absent target took 984 ms with a nested loop and 66 µs with two pointers. Without sortedness it is not slower, it is wrong.

A sliding window is the same idea for contiguous runs, and its precondition is monotonicity — the tracked property must move one way as the window grows. On a quantity that moves both ways, shrinking is unsound.

For repeated range queries over unchanging data, precompute: a prefix-sum table turns any range sum into one subtraction. Measured, 20,000 such queries over 100,000 values took 732 ms recomputed directly, against 0.7 ms to build the table plus 0.9 ms to answer them all. An update invalidates it — the gap tree-shaped range indexes fill.

You can also binary search the answer rather than the data, when checking a candidate is cheap and feasibility is monotone. Strings reuse these ideas: a trie stores keys by character path, so a prefix query walks the prefix and reads the subtree below. Over 50,000 words the prefix "mno" resolved 1,201× faster than scanning — but "a", matching 1,791 words, only 1.9× faster. A trie buys narrowing, not output.

Rule: before writing a nested loop, ask whether the data is ordered, whether the tracked quantity is monotone, and whether a range is queried twice.

Start with the sharpest distinction. A problem is undecidable when no program decides it on every input in finite time — whether an arbitrary program halts is the standard example. That is a different claim from "we know of no fast algorithm", where the famous hard problems sit.

The class P holds problems solvable in polynomial time. Nondeterministic polynomial time (NP) holds decision problems whose yes-answers can be verified quickly from a short certificate — the United States National Institute of Standards and Technology defines it as the class whose answers can be checked in polynomial time. Whether checking quickly implies finding quickly is open.

Reduction connects them, and its direction is where people go wrong. To show your problem is hard, convert a known-hard problem into yours: if solving yours cheaply would solve that one cheaply, yours is at least as hard. The other way proves nothing, since easy problems reduce to hard ones all the time.

The consequence is a decision. Suppose your scheduling, packing or routing problem sits in this family: stop hunting for an exact fast algorithm and choose an approximation, a heuristic, or a reformulated problem — the constraint making it hard is often one nobody needs. Hardness is only a worst-case statement, so solvers still handle large instances daily.

Rule: when a problem resists, ask whether it is undecidable, believed hard, or just badly stated — the third is the most common.