Algorithms and data structures

An interface is a promise about time. The list scrolls, the search box suggests, the map redraws. Behind each promise sits a choice about which structure holds the data, and that choice decides how it behaves when the data grows.

The working instrument is complexity: how the work grows with the input, on a stated model of what counts as one step. Used honestly it predicts. Used carelessly it certifies. Around it sits a small set of standard structures, each answering one question: what does this interface do, and how often?

Complexity is a claim you can be wrong about

Big-O notation describes how running time grows with the input, ignoring constant factors and small inputs. Three qualifications matter.

The first is which case. A worst case bounds every input. An average case needs a model of how inputs arrive. An amortised cost spreads one expensive operation over the cheap ones that preceded it (Cormen, Leiserson, Rivest and Stein, 2022). Appending to a growable array is O(1) most of the time, O(n) when the array doubles, and O(1) amortised. When an append lands on the wrong frame the user sees a stutter: the amortised figure and the worst case describe two experiences of the same code.

The second is the model: a constant is not small when the constant is a disk seek, and two structures with comparable asymptotics behave differently because one reads sequentially and the other seeks (Kleppmann, 2017).

The third is the disagreement. The contested question here is whether worst-case or expected-case behaviour should guide design. Cormen and colleagues present hash tables as constant time on average and linear in the worst case, while Fredman, Komlos and Szemeredi proved that a sparse table can be stored with constant worst-case access time (Fredman, Komlos and Szemeredi, 1984). An expected bound is a claim about a distribution of keys, and an interface whose keys are typed by users is not obviously inside any such distribution.

The worked case is a list that de-duplicates 200,000 rows. A nested loop compares every pair, about twenty billion comparisons; one pass with a hash set does 200,000 lookups. Predict both, then time both.

The structure follows the operation

An array stores elements contiguously, so reaching index i is arithmetic and scanning is fast, while inserting in the middle moves everything after it. A linked list stores nodes that point at each other, so inserting is cheap once you hold the node, but reading the thousandth element walks a thousand links.

A stack is last in, first out, which is the shape of undo: the most recent action is the first reversed. A queue is first in, first out, the shape of a work list, and a bounded queue protects a server when arrivals outrun processing. A deque allows work at both ends, which is what a navigation history needs, because backward and forward are the two ends of one sequence (Sedgewick and Wayne, 2011).

The worked case is the undo stack, where the hard decisions are not about the stack. An edit after three undos must discard the redo branch, so the history is a deque with a cursor rather than a pure stack. An entry must also record an operation in a form that can be inverted, not a snapshot of the document, or the memory cost of the history grows with the document rather than the edit.

Hashing, collisions and why autocomplete feels instant

A hash table computes a bucket number from a key, so a lookup goes to a calculated address instead of searching. Two keys can land in the same bucket, and handling that collision is the design decision: chaining keeps a list per bucket, while open addressing probes onward for a free slot. The load factor decides how much of either is needed, so the table is grown and its keys rehashed as it fills (Cormen, Leiserson, Rivest and Stein, 2022). Rehashing is the amortised part.

Constant-time lookup changes what an interface can afford. Autocomplete that scans a list of city names answers in proportion to the list; autocomplete that keys a map from prefix to matches answers in proportion to the prefix. Both are constant time per keystroke and differ by orders of magnitude in space, because the prefix map stores an entry for every prefix. The ordered alternative is a trie, in which each character selects a branch, so the work follows the query length and words that share a prefix share storage (Sedgewick and Wayne, 2011).

Trees, balance and the index under the map

A binary search tree halves the remaining keys at each step, giving logarithmic operations while it stays shallow. Insert sorted keys and it becomes a linked list, and every operation is linear. Balanced trees rearrange nodes as the shape changes.

Bayer and McCreight's B-tree carried the idea into databases, with reasoning about hardware rather than mathematics. They assumed the index sits on a disk, sized the nodes to the device, and reported retrieval, insertion and deletion in time proportional to the logarithm of the index size to base k, where k is a device-dependent number chosen for near-optimal performance, with storage utilisation of at least 50 per cent and experiments on indexes up to 100,000 keys (Bayer and McCreight, 1972). Wide shallow nodes mean few seeks.

Spatial data needs a different index, because a map query asks which objects fall inside a rectangle rather than which key matches. Guttman's R-tree groups nearby objects under bounding rectangles, so a window query descends only the branches whose rectangle overlaps it. He motivates it from computer-aided design and geo-data applications, and reports that his tests indicate good performance (Guttman, 1984). Mapping uses it to draw a viewport; collision detection uses it in the broad phase, to discard pairs that cannot touch.

The worked case is a million map markers. Testing each marker against the viewport is a million comparisons per pan, visible as stutter. Indexing the markers touches the ones returned plus the branches descended. The measurement that shows a large saving also exposes the smaller cost the index adds to every insertion.

Heaps and who goes first

A heap is a complete binary tree held in an array, with each parent outranking its children. It returns a minimum or maximum in constant time and inserts or removes in logarithmic time, without keeping the elements sorted. That is the right bargain for a priority queue, which needs the next item, not the whole order (Sedgewick and Wayne, 2011).

Task schedulers, notification ranking and job queues are priority queues. Selecting the ten highest-priority items from fifty thousand by sorting costs a full sort; a heap of size ten costs one pass. The subtlety is ties. A heap promises no order among equal keys, so two notifications with the same score can change places between runs, and an interface that reorders equal items on every refresh has destroyed the user's place. The repair is a second key, such as arrival time, that makes the comparison total (Cormen, Leiserson, Rivest and Stein, 2022).

Graphs answer questions that do not look like graph questions

A graph is vertices plus edges. Breadth-first search explores in rings of distance, and so answers degree of separation and finds shortest paths where every edge costs the same. Depth-first search goes deep first, and with three states per node it detects a cycle (Sedgewick and Wayne, 2011).

Dependency resolution is the clearest case. A set of dependencies is a directed graph, and a valid build order is a topological order of it, which exists exactly when the graph contains no cycle. The worked case is a package installer: a depth-first traversal that meets a node already on the current path has found the cycle, and the useful error names the cycle rather than reporting that resolution failed.

Social features traverse the same structure from the other direction, and the honest note is that breadth-first search over a whole social graph fans out explosively, so real products bound the search by depth or by invitation.

Sorting, searching and when to let the database do it

Comparison sorting cannot beat n log n in the worst case. Quicksort is fast in place and quadratic on adversarial input. Merge sort guarantees n log n and keeps equal keys in their original order (Cormen, Leiserson, Rivest and Stein, 2022). Stability is an interface property, because it decides whether a second sort by another column destroys the first.

The larger decision is where the sort happens. An index is a sorted structure the database maintains as rows change, which is why a query for the newest fifty rows can read them in order instead of sorting half a million (Kleppmann, 2017). Sorting in application code means moving every row out of the database to discard nearly all of them. Kleppmann's storage chapter compares a hash index, a log-structured variant and the B-tree, and the recurring trade is that the structure which makes reads cheap makes writes more expensive (Kleppmann, 2017).

The worked case is a message list ordered by time. Fetching every row and sorting in the client moves 500,000 rows across the network; ordering by an indexed column with a limit moves fifty. The index is not free, and the next write pays for it.

Recursion becomes affordable once subproblems are remembered

A recursive solution expresses a problem in terms of a smaller instance of itself, and its limit is the call stack: a directory walk over a deep tree exhausts it, while the same traversal with an explicit stack does not.

Memoisation stores a function's result against its arguments, so a repeated subproblem is answered from a table rather than recomputed. That is the trick behind dynamic programming: a problem that appears exponential becomes polynomial once its subproblems are identified and their answers reused (Cormen, Leiserson, Rivest and Stein, 2022).

Text comparison is the canonical case. Wagner and Fischer defined the distance between two strings as the minimum cost sequence of substitutions, deletions and insertions turning one into the other, and gave an algorithm whose time is proportional to the product of the two lengths (Wagner and Fischer, 1974). A diff is the same family of problem solved with the size of the difference in mind. Myers showed that the shortest edit script and the longest common subsequence are dual problems, equivalent to a shortest path in an edit graph, and gave an algorithm costing time and space proportional to N times D, where N is the sum of the lengths and D the size of the minimum edit script (Myers, 1986). It is fast precisely when the two versions are similar, so the intuition that diffing must be quadratic is wrong when the files are close.

Fuzzy search separates ranking from searching, and measurement separates prediction from hope

The naive way to find a pattern in a text is quadratic in the worst case, because each mismatch discards what it learned. Knuth, Morris and Pratt preprocess the pattern into a shift table, so the text is scanned once and the work is proportional to the sum of the two lengths. They report a constant low enough for practical use, and also consider faster average-case methods (Knuth, Morris and Pratt, 1977).

Users do not type exactly. Edit distance is the right way to rank a near miss and the wrong way to search a large corpus, so fuzzy search in practice indexes short character sequences and uses distance to re-rank a small candidate set. A search for "Glagsow" must return "Glasgow" rather than "Glass": trigrams narrow the candidates, and a distance threshold of one or two decides which are shown.

Predict, then check. Record the size of the data, report percentiles rather than an average, because the slowest one per cent is somebody's experience on every visit, and note whether the run was warm or cold. Whether that is fast enough is not a property of the code. Miller observed that the literature abounded in controversy about the limits of response time, and that part of the disagreement was semantic: different purposes admit different acceptable response times, so the useful question is response time for what (Miller, 1968). One target for a keystroke suggestion, a page of results and a background export is a category error.

The structures here are the ones an application can hold in memory. Once the data is larger than memory, or shared between users, the index belongs to a database, with its own decisions about how it stores, orders and retrieves what the interface asks for.