Data Structures & Algorithms

Branch: Computer Science Foundations (Quant-Code galaxy) · Node CS1.05 · ~22 focused hours · CROWN node · Mastery gate ≥ 90%

There is a moment in every analyst's coding life when the machine stops being fast. The notebook that returned in two seconds on last month's file has been running for eleven minutes on this month's, and nothing is wrong with the logic or the machine. What is wrong is a choice, a list where a dictionary belonged, a pop(0) where a head pointer belonged, a nested loop where a single pass belonged, and that choice was invisible at small n and is fatal at large n. This node is about making that choice consciously, forever, by building the structures yourself until their costs are not memorised but obvious.

That is the practical case. The second one is why this node wears a crown: data structures and algorithms is the most heavily examined subject in quantitative and engineering hiring, and for a defensible reason. It is the only body of knowledge that simultaneously tests whether you can reason about cost before you run anything, whether you can prove your reasoning is right, and whether you can turn a proof into working code under time pressure. An analyst who can say "that is a heap, it will be O(n log k), and here is why the naive version is O(n log n) with worse memory" is playing a different game from one who writes the loop and hopes.

So this node has an unusually strict rule, and it is the rule that earns the crown: every structure here you implement from scratch, and every cost claim you make you prove. Not "a heap is fast", a heap of n items has height ⌊log₂ n⌋, sift-down walks one root-to-leaf path, so push and pop are O(log n), and Floyd's bottom-up build is O(n) because the nodes at height h number at most ⌈n/2^(h+1)⌉ and Σ h/2^h converges to 2. You will write that proof out, then write the heap, and then a hidden test will check that your array layout is exactly the one Floyd's algorithm produces, because a sorted list also satisfies the heap property, and we are not interested in a structure that only looks right.

Every problem here is finance-flavoured, and not decoratively. FIFO tax-lot matching is a queue. An order book is a balanced tree over price levels. "My ten largest exposures" is a bounded min-heap. A three-statement model is a topological sort of a dependency DAG. Triangular currency arbitrage is a negative cycle under a logarithmic transform. These are not analogies dressed up to make the material palatable; they are the same objects, and once you see that, a library of solved problems becomes available to you at the desk.

Code pack: this node ships with CS1.05 (app/public/code-packs/CS1.05.json): ten graded exercises, CS1.05-e01 through CS1.05-e10, each with hidden tests that a hardcoded answer cannot survive and a size that a wrong-complexity answer cannot finish. The exercises are the assessment; this document is the argument that makes them passable.

Learning objectives

By the end you can:

1. State a cost model and reason inside it. Given a code fragment, name the dominant operation, count it against input size, and state time and space complexity, and say what the constant factor and the memory hierarchy do to that claim in practice.
2. Implement, from scratch and correctly, the seven core structures: dynamic array, hash map with collision resolution, stack, queue (ring buffer) and deque, linked list, binary search tree, and binary heap, each with its full operation set and its per-operation cost justified, not asserted.
3. Prove amortised bounds. Show by the aggregate and the accounting method that append on a doubling array is O(1) amortised, that the monotonic-deque sliding window is O(n) despite an inner loop, and why the shrink threshold must be a quarter rather than a half.
4. Analyse hashing honestly: expected O(1) under simple uniform hashing with expected chain length equal to the load factor α, worst case O(n), and the adversarial and clustering cases that turn one into the other.
5. Reason about trees by height: derive the O(height) bound, show that a randomly built BST has expected height Θ(log n) while sorted insertion gives exactly n − 1, and state what a self-balancing tree (AVL, red-black, B-tree) buys and costs.
6. Prove Floyd's O(n) heap construction and use a bounded heap for top-k in O(n log k) time and O(k) space.
7. Traverse and search graphs: adjacency list versus matrix, BFS/DFS at O(V + E), topological sort by Kahn's algorithm with free cycle detection, Dijkstra, Bellman-Ford with negative-cycle detection, and union-find with path compression.
8. Search and sort with the bounds proven: binary search's O(log n) and its loop invariant; insertion, merge, quick and heap sort with recurrences solved; the Θ(n log n) comparison lower bound proven by decision tree; and the linear-time non-comparison sorts and when they apply.
9. Apply the three paradigms: divide and conquer (with the master theorem), greedy (with an exchange-argument proof and a counterexample where greedy fails), and dynamic programming (optimal substructure plus overlapping subproblems, then memoisation or tabulation).
10. Choose the right structure for a stated operation profile and defend it out loud at interview standard, including the second-order considerations (stability, cache behaviour, memory, worst versus expected case) that separate a correct answer from a good one.
11. (Productivity objective: R10 duality.) Use a coding copilot on this material the way a working developer does, after you can do it by hand, and review its output for the failure modes specific to algorithmic code: plausible-but-wrong boundary conditions, silently quadratic "optimisations", and hallucinated standard-library APIs.

The duality, stated once (R10). The gated skill is objectives 1–10, and the gate is deliberately hostile to shortcuts: the code-pack hidden tests check array layouts, exact resize ladders and closed-form invariant counts that a generated answer will not reproduce by luck, and they run at sizes where a wrong-complexity answer simply does not finish. Objective 11 is the payoff you keep. The app never calls an AI at runtime, the callouts below ask you to generate something in your own tool, paste it back, and let the local hidden tests grade it. The machine drafts, the tests judge, and you are the one who has to know why it failed.

Prerequisites & connections

Builds on. CS1.01 and CS1.02 for Python itself, functions, classes, dunder methods, and the built-in list/dict/set you are about to build from scratch. CS1.03 for what memory actually is: stack versus heap, pointers and indirection, and why a contiguous block behaves differently from a chain of scattered nodes. And above all CS1.04, which owns Big-O notation, recursion and the mechanics of asymptotic analysis. This node does not re-derive what Big-O means or how to unroll a recursive call; if T(n) = T(n−1) + O(1) is not yet an automatic read, go back, one clean hour there makes this node twice as fast. What CS1.05 adds is the hard analysis CS1.04 deliberately left alone: amortised argument, the master theorem, expected-case analysis, and information-theoretic lower bounds.

Cross-links, not duplications (R1). Where an argument is probabilistic, expected chain length in a hash table, the expected height of a randomly built BST, why randomised quicksort is Θ(n log n) expected and Θ(n²) worst, the underlying probability is derived once in QM1.01 and QM1.02 and used here: this node states the assumption, applies the result, and points at the derivation. Likewise the finance semantics: FIFO versus LIFO cost-basis rules belong to the accounting and tax nodes, order-book microstructure to QD2.01, drawdown as a risk statistic to QD2.02. Here they are shapes of computation, each named so you can follow it home.

Feeds forward. Immediately into CS2.03 (databases and SQL), where a B-tree index is a shallow tree over sorted keys and a hash join is the hash map you build in CS1.05-e02. Into CS2.04, where cache lines, row-versus-columnar layout and external sorting are the same trade-offs at a different scale. Into CS2.06, where the fastest way to catch a subtly wrong generated function is to know what its complexity should be. And structurally into the quant-developer branch: QD1.03's event-driven backtester is a priority queue of timestamped events, QD1.04's optimiser lives or dies on an inner loop, QD2.01's limit order book is exactly the tree-plus-queue design taught here, and QD2.05's capstone will not run in acceptable time if you have chosen wrong. This is the node whose absence you feel everywhere else.

Core teaching content

The cost model an analyst actually needs

Start with the machine, because every complexity claim is a claim about a machine. The model we use (the RAM model) says a fixed set of primitive operations (arithmetic, comparison, assignment, following a reference, reading or writing one array slot at a known index) each cost one unit, and we count how many units an algorithm performs as a function of its input size n. Big-O then throws away constants and lower-order terms, which is either a scandalous simplification or the most useful abstraction in computing depending on how you use it.

Use it like this. Asymptotics decide the algorithm; constants decide the implementation. No amount of tuning rescues an O(n²) algorithm at n = 10⁶ (that is 10¹² operations, hours to days) while a 3× constant-factor difference between two O(n log n) implementations is survivable. So the first question is always what is the shape, and only then what is the constant. As an order-of-magnitude calibration (not a benchmark, measure your own machine): interpreted Python runs very roughly 10⁷ simple operations per second, compiled or vectorised code 10⁸–10⁹. Against that, n = 10⁴ is free at O(n²); n = 10⁶ is comfortable at O(n log n) and impossible at O(n²); n = 10⁹ needs O(n) and careful memory.

Three refinements matter enough to name now. First, worst case versus expected case: hash lookup is O(1) expected and O(n) worst, quicksort Θ(n log n) expected and Θ(n²) worst, and in finance, where data arrives sorted by date and grouped by ticker far more often than randomly, the "unlucky" input is the normal one. Second, amortised cost, which is not average cost: an amortised bound is a proven guarantee about any sequence of operations, with no probability involved. Third, the memory hierarchy, which the RAM model pretends does not exist, an L1 hit and a main-memory read differ by roughly two orders of magnitude, and a contiguous array walk gets the fast path while a linked-list walk gets the slow one. That is why an O(n) array scan routinely beats an O(log n) pointer-chase at small and medium n, and it is the largest single gap between textbook complexity and observed runtime.

Space is counted the same way, usually as auxiliary space, what the algorithm allocates beyond its input. Merge sort is Θ(n log n) time and Θ(n) auxiliary space; heapsort is Θ(n log n) time and Θ(1). With room to spare that difference is invisible; on a 40 GB tick file it decides which algorithm you are allowed to use at all.

Arrays: contiguity, and the amortised append proven two ways

An array is one contiguous block of memory holding equal-sized slots. That single physical fact generates the whole cost table. Because slot i sits at base + i × slot_size, indexing is one arithmetic operation and one memory read: O(1), and cache-friendly. Because the block is contiguous, inserting or deleting in the middle must shift every following element: O(n). Because the block has a fixed size, appending past the end requires a new, larger block and a full copy: O(n) for that one append.

Which raises the question this section exists to answer: Python's list.append is described as O(1), yet it sometimes copies everything. Both are true, and the reconciliation is amortised analysis. The rule is doubling: when the block is full, allocate one of twice the capacity and copy across. Now count the total work of n appends. The copies happen at sizes 1, 2, 4, 8, …, up to the largest power of two below n, so total elements copied is 1 + 2 + 4 + ⋯ + 2^k < 2^(k+1) ≤ 2n. Add the n single-slot writes and total work is under 3n. Divide by n and each append costs O(1) amortised. That is the aggregate method: total the sequence, divide by its length.

The accounting method gives the same answer with more intuition. Charge every append 3 units: one pays for writing the new element, and two are banked as credit on that element. When an array of capacity c fills and doubles, the c/2 elements added since the last doubling each carry 2 banked units, exactly c units, exactly the c copies the resize performs. The balance is never negative, so 3 is a genuine upper bound. Notice the argument proves something stronger than an average: it holds for every sequence of appends, adversarial ones included.

Two consequences to keep at your fingertips. Growth must be multiplicative. Grow by a constant (say 1,000 slots) and the copies become 1,000 + 2,000 + 3,000 + ⋯, an arithmetic series summing to Θ(n²/2): quadratic, which CS1.05-e01's hidden tests catch by asserting the capacity ladder. Shrinking must hysterise. Halve the capacity as soon as the array is half full and an alternating pop/append at the boundary triggers a full copy every operation, forever. Shrink instead at one quarter full and, after any resize, the array must gain or lose at least half its elements before the next one, so the Θ(n) copy is spread over Ω(n) operations and amortised O(1) is restored.

The finance reading: a tick tape, a fill blotter, a returns series (anything you append to in a loop and then index) is an array. It is also why df.append in a loop is a known pandas anti-pattern (each call rebuilds the frame, Θ(n²) overall) while building a Python list and constructing the frame once is Θ(n).

Hash maps: the O(1) that is only ever expected

A hash map answers "what value is stored under this key?" without searching. A hash function turns the key into an integer; that integer modulo the number of buckets m gives a slot; the value goes there. Ticker → position, date → row index, (strategy, date) → P&L: this is the workhorse structure of applied analytics, and it is worth knowing exactly which promise it makes.

Collisions are certain, not exceptional. Any function from a large key space to m buckets must map different keys together, and the birthday paradox makes it happen early: with 365 buckets and only 23 random keys, a collision is already more likely than not. Two families of resolution exist. Separate chaining keeps a list per bucket, simple, tolerant of α > 1, one dereference per probe. Open addressing stores everything in the table itself and probes onward on collision (linear, quadratic or double hashing), better cache behaviour and no per-node overhead, but it degrades sharply as the table fills and deletion needs tombstones. CPython's dict uses open addressing; CS1.05-e02 has you build the chaining version, because chaining makes the analysis visible.

Now the proof. Let n be the stored keys and m the buckets, and define the load factor α = n/m. Under the simple uniform hashing assumption (each key equally likely to land in any bucket, independently) the expected number of keys in a given bucket is n × (1/m) = α, by linearity of expectation (QM1.01 derives it; we use it). A lookup costs the O(1) hash plus a walk of that chain, so its expected cost is Θ(1 + α). Keep α bounded (which is exactly what the resize rule does) and lookup, insert and delete are expected O(1). Note what has not been proven: the worst case is still Θ(n), because nothing forbids every key landing in one bucket. Under random keys that is astronomically unlikely; under keys chosen by someone who knows your hash function it is trivially arrangeable, which is why production hash functions are randomly seeded per process.

Resizing keeps the promise. When α passes a threshold (0.75 is the common choice, and the one CS1.05-e02 enforces), allocate 2m buckets and re-insert every entry. Re-insert, not copy: the index is hash(k) % m and m has changed, so almost every key moves. The rehash costs Θ(n) but happens rarely enough (same doubling argument) to be O(1) amortised. The exercise pins the exact ladder (six keys in eight buckets is α = 0.75 and does not resize; the seventh takes α to 0.875 and doubles) because a map that never grows passes every correctness check and then quietly degrades to a linear scan.

What a hash map cannot do: anything ordered. No "next key after this one", no "all keys between ₹1,240 and ₹1,260", no in-order iteration. Hashing deliberately destroys order to buy O(1). When you need order back, you need a tree, and that trade is the subject of two sections from here.

Stacks, queues, and the monotonic trick

A stack is last-in-first-out: push, pop, peek, all O(1) on the end of an array. Its finance appearances are structural rather than glamorous, evaluating a nested formula, undo history, LIFO cost-basis matching, and above all the explicit stack you use to convert a recursive tree or graph walk into an iterative one when the recursion depth would overflow.

A queue is first-in-first-out, and it is where the naive implementation costs you. list.append plus list.pop(0) is a queue, and pop(0) shifts every remaining element: Θ(n) per dequeue, Θ(n²) to drain. The fix is a ring buffer, a fixed block with a head index and a size, where enqueue writes at (head + size) mod capacity and dequeue reads at head and advances it modulo capacity. Nothing shifts; both are O(1) worst case. CS1.05-e03 has you build it and then drain a 200,000-deep queue, a size at which the pop(0) version cannot finish. FIFO tax-lot matching sits directly on top: buys enqueue lots, a sell consumes the oldest lots first, and a partially consumed lot stays at the head with its quantity reduced. Swap the queue for a stack and you have LIFO, same code shape, materially different realised gain, which is why the convention is a tax election and not a detail.

A deque allows O(1) insertion and removal at both ends, and it unlocks the one genuinely clever idea here: the monotonic deque. To compute the maximum of every length-w window of a price series, the obvious loop is max(prices[i:i+w]) for each i, which is Θ(n·w), at n = 300,000 and w = 5,000 that is 1.5 × 10⁹ comparisons and it will not finish. Instead keep a deque of indices whose prices are strictly decreasing. For each new price: pop from the back while the back's price is ≤ the incoming one (a larger, later value dominates them for the rest of their lives), append the new index, drop the front if it has aged out of the window, and read the window maximum off the front.

The proof is a small amortised argument, worth doing carefully because the code looks quadratic, a while inside a for. But each index is appended exactly once and removed at most once, so the inner loop performs at most n pops across the entire run. Total work is at most 2n operations. Θ(n), independent of w. That is CS1.05-e04, and the same shape solves "largest rectangle in a histogram", "next greater element" and "how long since the last new high" (the underwater-duration statistic in a drawdown report). Maximum drawdown itself needs no deque: carry the running peak and the worst (peak − price)/peak in a single Θ(n) pass, which is the second half of that exercise.

Linked lists: the structure that wins on paper and loses on silicon

A singly linked list is a chain of nodes, each holding a value and a reference to the next. Against the array it reads beautifully: O(1) insert or delete at a known position (rewire two references; nothing shifts) and O(1) push/pop at the front, where the array is O(n). Its weaknesses are equally structural: O(n) indexing, because reaching element i means following i references, and O(n) search with no possibility of binary search, since you cannot jump to the middle.

The honest modern verdict is that linked lists lose most practical contests to arrays, and the reason is not in the complexity table, it is the memory hierarchy. Array elements are contiguous, so one cache-line fetch brings in several and the prefetcher predicts the walk; list nodes are scattered, so each hop is a potential cache miss on top of a per-node pointer overhead. A miss costs on the order of a hundred hits, so "O(n) with a good constant" beats "O(n) with a terrible constant" decisively, and beats O(log n) pointer-chasing at surprisingly large n.

Learn them anyway, for three reasons. They are the substrate for other structures, hash-map chains, adjacency lists, allocator free lists. The doubly linked list genuinely wins when you hold a reference to a node and need O(1) removal without a search, which is exactly how an order-book price level maintains time priority under cancellations: a cancel arrives holding a pointer to its own order, which leaves the queue in constant time without disturbing anyone's position. And they are the reference point that makes the next structure make sense, a binary search tree built from sorted input is a linked list, and the whole discipline of balancing exists to stop that happening.

{
  "skill": "Implementing a classic data structure you already understand, then hardening it against the edge cases",
  "use": "Once you can write the structure by hand, use a coding copilot to (a) generate an adversarial test list for it — empty, single-element, duplicate-key, wraparound, resize-boundary, capacity-1 — and (b) draft an alternative implementation you can diff against yours to find your blind spot. Generate it in your own tool, paste your final code back here, and let this node's hidden tests grade it locally.",
  "tools": ["Chat assistants — Claude, ChatGPT, Gemini", "IDE copilots — GitHub Copilot, Cursor, JetBrains AI", "Your own editor plus this node's code pack (CS1.05) as the grader"],
  "prompt": "I have implemented <STRUCTURE> with this API: <SIGNATURES>. Do NOT write my implementation. Instead: (1) list every edge case and boundary condition a correct implementation must handle, with the specific input that triggers each; (2) for each, state the WRONG output a common buggy implementation would give; (3) name the exact time and space complexity each operation should have and the input pattern that would expose a wrong-complexity implementation.",
  "verify": "Run every generated edge case against your own code and confirm the complexity claims by timing at two sizes an order of magnitude apart — if 10x the input costs ~100x the time, you have written a quadratic. Copilots routinely emit list.pop(0) for a queue, forget to rehash on resize, and invent standard-library methods that do not exist; check every API call against the real documentation before you trust it (Primary-Source Guardrail: Trace, Recompute).",
  "diy": "Gated: you must have implemented and passed CS1.05-e01 through e03 by hand first. The by-hand version is what tells you whether the generated edge-case list is complete or plausible-sounding nonsense.",
  "market": "IN"
}

Trees: when you need order as well as lookup

A binary search tree stores keys under one invariant: for every node, all keys in its left subtree are smaller and all in its right subtree are larger. That invariant does all the work. Search walks down from the root, comparing once per level and discarding half the remaining structure at each step; insert walks the same path and hangs a new leaf; and an in-order traversal emits every key in sorted order, the property a hash map can never offer.

The complexity is entirely a function of height. Search, insert and delete each follow exactly one root-to-leaf path, so each is O(h) where h is the height in edges. Everything hinges on what h is, and the answer spans the whole range:

• Best case: perfectly balanced. A tree of height h holds at most 2^(h+1) − 1 nodes, so n nodes require h ≥ ⌈log₂(n+1)⌉ − 1; balanced trees achieve it and operations are Θ(log n): 20 comparisons at n = 1,000,000.
• Worst case: keys inserted in sorted order. Each new key is larger than everything before it, becomes the right child of its predecessor, and the tree is a chain of height n − 1 with every operation Θ(n). CS1.05-e06 inserts 400 ascending keys and asserts height() == 399, because this is not a curiosity: financial data arrives sorted by date essentially always, so a naive BST keyed on date is a linked list every single time.
• Expected case: uniformly random insertion order gives expected height Θ(log n) (constant ≈ 4.31 ln n, a standard randomised-analysis result resting on the probability tools of QM1.01). At n ≈ 500 that is about 23, which is why CS1.05-e06 asserts a randomly built tree's height lands in [8, 44], a band a real tree hits and a sorted list or a dictionary in disguise cannot.

That gap between 20 and 1,000,000 is the entire motivation for self-balancing trees. An AVL tree keeps every node's two subtree heights within 1 of each other via O(1) rotations (local rewirings that change shape without violating the ordering) guaranteeing h ≤ 1.44 log₂ n. A red-black tree enforces a looser colour invariant for h ≤ 2 log₂(n+1) with fewer rotations, which makes it the standard-library choice (C++ std::map, Java TreeMap). A B-tree widens each node to hold many keys so one node fills one disk page or cache line, cutting the number of expensive fetches rather than the number of comparisons, which is why every database index in CS2.03 is a B-tree. You are not asked to implement balancing; you are asked to know what it costs (a constant factor on insert, plus code complexity) and what it buys (a worst-case guarantee instead of an expected one).

The operation that justifies the whole structure is the range query: every key between lo and hi, in order, impossible in a hash map without scanning everything. In a BST it is a pruned in-order walk (never descend left from a node whose key is ≤ lo, never right from one whose key is ≥ hi), costing O(h + k) for k results. That is CS1.05-e06, whose hidden test runs three thousand narrow window queries against a 100,000-node tree, a workload an unpruned "traverse then filter" implementation cannot finish. The finance reading is direct: an order book is price levels in a balanced tree (best bid and best ask are the max and min, one edge away), each level holding a FIFO queue of orders. Tree for price priority, queue for time priority, the two structures of this node, composed.

Heaps: the top-k structure, and Floyd's linear build

A binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) satisfying the heap property: every node is ≤ both its children (a min-heap). Completeness lets you throw the pointers away and store the tree in a flat array, where the children of index i are 2i+1 and 2i+2 and the parent is (i−1)//2. No node objects, no allocation, perfect cache locality.

Because it is complete, a heap of n nodes has height exactly ⌊log₂ n⌋. Two repair operations maintain the invariant, and each walks at most one root-to-leaf path:

• sift_up(i): while i's parent is larger, swap and move up. O(log n).
• sift_down(i): while a child is smaller, swap with the smaller child (swapping with the larger one breaks the invariant on the other side) and move down. O(log n).

push appends and sifts up; pop saves the root, moves the last element to the root, shrinks the array and sifts down. Both O(log n); peek is O(1). Note what a heap deliberately does not give you: any order beyond the root. Finding an arbitrary key is O(n). It is a priority structure, not a search structure.

Now the crown proof: building a heap from n arbitrary items costs Θ(n), not Θ(n log n). The naive build pushes each item, n pushes at O(log n) each, Θ(n log n). Floyd's bottom-up build instead calls sift_down on every internal node from n//2 − 1 down to 0. It looks similar; it is not. The cost of sift_down at a node is proportional to that node's height, and in a complete tree the vast majority of nodes are near the bottom, where the height is nearly zero. Precisely: the number of nodes at height h is at most ⌈n / 2^(h+1)⌉. So the total is

Σ_{h=0}^{⌊log₂ n⌋} ⌈n / 2^(h+1)⌉ · O(h) = O( n · Σ_{h≥0} h / 2^h ).

The series Σ_{h≥0} h/2^h converges to 2 (differentiate the geometric series Σx^h = 1/(1−x) to get Σ h·x^(h−1) = 1/(1−x)², then set x = ½ and multiply by ½). So the total is O(2n) = Θ(n): asymptotically free. CS1.05-e05 checks this by asserting your array equals exactly the layout Floyd's algorithm produces, on seeded inputs, because a sorted list also satisfies the heap property and we want the structure, not a lookalike.

The application that pays for the section is top-k. "The ten largest exposures in a 400,000-row blotter." Sorting is Θ(n log n) time and Θ(n) space. A bounded min-heap of size k is better: push the first k, then for each remaining value compare it to the root (the weakest survivor) and if it is larger, pop and push. Each item costs at most O(log k), giving Θ(n log k) time and Θ(k) space; at n = 400,000 and k = 10 that is log₂k ≈ 3.3 against log₂n ≈ 18.6, and memory drops from 400,000 slots to 10. The counter-intuitive move (a min-heap to find maxima) generalises to k-way merging of sorted return series, k-nearest-neighbours, and the k most active symbols in a tick stream. Heapsort falls out too: build in Θ(n), pop n times at Θ(log n). Θ(n log n) with Θ(1) auxiliary space, the in-place guarantee merge sort cannot make. And an event-driven backtester (QD1.03) is nothing but a heap keyed on timestamp, which is why that node depends on this one.

Graphs: dependency, arbitrage and connectivity

A graph is a set of vertices and edges, directed or not, weighted or not. Two representations, and the choice is about density. An adjacency matrix is a V×V table: O(1) edge lookup, Θ(V²) space, and neighbour iteration costs Θ(V) whether a vertex has two neighbours or two hundred. An adjacency list stores each vertex's neighbours: Θ(V + E) space, iteration proportional to degree, O(degree) edge lookup. Real financial graphs are sparse (a handful of subsidiaries, a few dozen quoted pairs, a model cell depending on three others) so adjacency list is the default, which is why the standard traversal bound is written O(V + E) rather than O(V²).

BFS and DFS are the same algorithm with a different container. Both mark vertices visited and expand outward; BFS uses a queue and so visits in order of increasing edge-count from the source (shortest paths in unweighted graphs), while DFS uses a stack, or the call stack, if you accept the depth risk, and dives to the bottom first. Each visits every vertex once and examines every edge once: O(V + E), O(V) space. Connectivity, reachability ("which entities does this exposure touch?") and cycle detection all fall out.

Topological sort is the one an analyst meets first: a three-statement model, a factor pipeline, a settlement chain, a directed acyclic graph of things that must be computed before other things. Kahn's algorithm computes in-degrees, seeds a ready set with the zero-in-degree vertices, then repeatedly emits a ready vertex and decrements its successors' in-degrees, adding any that reach zero. O(V + E), and here is the elegant part: cycle detection is free. Finish having emitted fewer vertices than exist and the remainder are locked in a cycle, a circular reference, so you return failure. One length comparison, not a second algorithm. CS1.05-e08 builds it with a smallest-ready-id tie-break so the answer is deterministic, and plants cycles at random positions in seeded DAGs.

Weighted shortest paths split on whether negative edges exist. Dijkstra repeatedly extracts the closest unfinalised vertex and relaxes its edges (O((V + E) log V) with a binary heap) and its correctness rests on a greedy exchange argument that requires non-negative weights: with a negative edge a vertex can be finalised and then improved, and Dijkstra never goes back. Bellman-Ford relaxes every edge V − 1 times, O(V·E), slower, and worth it because it tolerates negative weights and detects negative cycles. After V − 1 passes every shortest simple path has converged (a simple path visits at most V vertices, hence V − 1 edges), so if any edge still relaxes on one more pass, some path is improving forever, which only a negative cycle allows.

That detection is the finance payoff. Currency conversion multiplies rates; shortest-path algorithms add weights. Take logarithms and they become the same problem: weight the quote "one unit of A buys r units of B" as w = −log r, and a cycle multiplies to Π rᵢ > 1 exactly when Σ(−log rᵢ) < 0. Triangular arbitrage is a negative cycle. Initialise every distance to 0.0 (a virtual source with a free edge to every currency, which lets the search find a negative cycle anywhere), run V − 1 passes, then sweep once more; any edge that still relaxes proves an arbitrage. That is CS1.05-e09, and it carries a floating-point lesson its hidden tests enforce: a perfectly consistent quote matrix produces cycle sums of ±10⁻¹⁵ from rounding alone, so without a tolerance your detector fires on every book it sees. Real desks then subtract the bid-ask spread from each leg, at which point most detected "arbitrage" evaporates, the tolerance is not a numerical hack but the first honest transaction cost.

Union-Find (disjoint sets) answers the other structural question: which things are connected? It keeps a forest with one representative per set; find(x) walks to the root and union(a, b) links two roots. Two optimisations make it nearly free, union by rank (attach the shorter tree under the taller, bounding height at O(log n)) and path compression (on the way back from a find, repoint every node directly at the root), giving O(α(n)) amortised, where α is the inverse Ackermann function and is under 5 for any n in this universe. It powers Kruskal's minimum-spanning-tree algorithm, and its analyst use is clustering: group assets whose correlation exceeds a threshold into connected exposure blocks, or collapse a web of intercompany holdings into ultimate beneficial groups, in one near-linear pass.

Searching: binary search, and binary search on the answer

Linear search is Θ(n) and needs nothing. Binary search is Θ(log n) and needs sorted input: compare the target to the middle element and discard half the array. The bound is immediate, the interval halves each step, so after k steps it holds n/2^k elements, and the search ends when that reaches 1, i.e. k = log₂ n. Twenty comparisons for a million elements; thirty for a billion.

Binary search is also the classic case of code that is easy to write and hard to write correctly, so write the invariant down before the loop: the target, if present, lies within [lo, hi). Every branch must preserve that and strictly shrink the interval, or you loop forever; mid = lo + (hi − lo)//2 rather than (lo + hi)//2 avoids overflow in fixed-width languages (C, in CS1.03). Note the amortisation trap too: sorting to enable one binary search is Θ(n log n) to save Θ(n), a loss. Sort once and search m times and you win as soon as m log n < n, which for large n is almost immediately. The same arithmetic decides whether a database index earns its keep (CS2.03).

The generalisation matters more to an analyst than the array version. Binary search on the answer applies to any monotone function: bond price is monotone decreasing in yield, so yield to maturity by bisection is exactly this, and the iteration count is a formula, not a mystery. Each step halves the bracket, so reaching tolerance ε from an initial bracket of width W takes ⌈log₂(W/ε)⌉ iterations, always, regardless of the function's shape. That is bisection's virtue: slower than Newton-Raphson (quadratic convergence, but it can diverge) and it cannot fail while the function is continuous and the bracket contains a sign change. For an IRR on a cash-flow stream with sign changes, "slow and cannot fail" is usually the right trade. Worked example 8 computes the count for a real tolerance.

Sorting: three algorithms, one lower bound

Sorting is where the three paradigms of the next sections first appear, and where the only proof in this node that is about all possible algorithms lives.

Insertion sort grows a sorted prefix, inserting each new element by shifting. Θ(n²) worst and average, Θ(n) on sorted input, Θ(1) auxiliary space, stable. Its virtue is adaptivity, its true cost is Θ(n + I) where I is the inversion count, so on nearly-sorted data (a tick file with a few late records) it is effectively linear. Every serious library switches to it below ~16 elements, where its tiny constant beats the recursion overhead of anything asymptotically better.

Merge sort splits in half, sorts both halves recursively, and merges. The recurrence T(n) = 2T(n/2) + Θ(n) is worth solving twice: by recursion tree, each level does Θ(n) merging and halving gives log₂n levels, so Θ(n log n); by the master theorem (next section), a = 2, b = 2, f(n) = Θ(n) and n^(log_b a) = n¹ matches f, so case 2 gives Θ(n log n). The bound holds in every case (worst, average, best) which is the guarantee quicksort cannot make. Merge sort is stable when the merge takes from the left half on ties, and that is not a triviality: exchanges match on price-time priority, so re-sorting a fill tape by price must preserve arrival order among equal prices or you have silently rewritten the queue. It costs Θ(n) auxiliary space, and it is the only one of the three that works when the data does not fit in memory, external merge sort streams sorted runs from disk, which is what a database does when it sorts more than it can hold (CS2.04).

The inversion count falls out of the merge for free: each time you take from the right half, every element still remaining in the left half is inverted against it, so add len(left) − i. Counting inversions separately is Θ(n²); counting them inside the merge costs nothing. That is CS1.05-e07, built so sorted() cannot pass it, the inversion count is a number the standard library will not give you, and the hidden tests use closed forms (a reversed array of n distinct keys has exactly n(n−1)/2 inversions; two swapped blocks of sizes a and b have exactly a·b) that cannot be hit by luck.

Quicksort partitions around a pivot and recurses on both sides. Θ(n log n) expected, Θ(n²) worst (an always-extreme pivot, exactly what first-element pivoting meets on sorted input, and financial data is sorted), Θ(log n) stack space, in-place, and not stable as normally written. Randomising the pivot makes the worst case require an adversary who can predict your seed rather than merely hand you sorted data, and its cache behaviour makes it the fastest of the three in practice in memory. Production sorts are hybrids: Timsort (Python's sorted and list.sort) is a stable, adaptive merge sort that detects existing runs and is Θ(n) on sorted input; introsort (C++) runs quicksort and switches to heapsort when recursion gets too deep, buying the Θ(n log n) worst case without losing quicksort's constant.

Now the lower bound, which is the crown-level result. Any sorting algorithm that only compares elements requires Ω(n log n) comparisons in the worst case. The proof is a decision tree. Model the algorithm as a binary tree whose internal nodes are comparisons and whose leaves are output permutations. To be correct it must be able to produce all n! permutations, so it has at least n! leaves. A binary tree with L leaves has height at least log₂ L, and the worst-case number of comparisons is the height. So comparisons ≥ log₂(n!), and by Stirling's approximation log₂(n!) = Θ(n log n). Merge sort and heapsort therefore are asymptotically optimal, and no cleverness will beat them within the comparison model.

The word "comparison" is doing the work, and stepping outside it is how the linear-time sorts exist. Counting sort tallies occurrences of each of k possible key values and reconstructs: Θ(n + k), useful when k is small, sorting a million trades by exchange code, or by rating bucket. Radix sort applies a stable counting sort digit by digit: Θ(d(n + k)) for d digits, which is how you sort a billion fixed-width integer timestamps or CUSIPs in linear time. These do not violate the bound; they simply do not compare, and they pay for it by requiring keys with exploitable structure.

Divide and conquer, and the master theorem

The pattern: split the problem into subproblems of the same kind, solve them recursively, combine. Its cost obeys T(n) = a·T(n/b) + f(n) (a subproblems of size n/b, plus f(n) to split and combine) and the master theorem solves that recurrence by comparing f(n) against n^(log_b a), the total work at the leaves:

1. If f(n) = O(n^(log_b a − ε)) for some ε > 0 (the leaves dominate) then T(n) = Θ(n^(log_b a)).
2. If f(n) = Θ(n^(log_b a)) (every level costs the same) then T(n) = Θ(n^(log_b a) · log n).
3. If f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ c·f(n) for some c < 1 (the root dominates) then T(n) = Θ(f(n)).

Read the three cases as one idea: work out whether the work concentrates at the top, at the bottom, or spreads evenly, and the answer follows. Merge sort is case 2 (a = 2, b = 2, f = n, n^(log₂2) = n): Θ(n log n). Binary search is case 2 with a = 1 (n^(log₂1) = 1, f = Θ(1)): Θ(log n). Blocked matrix multiplication is a = 8, b = 2, f = Θ(n²), n^(log₂8) = n³, case 1: Θ(n³), and Strassen's insight was to cut a from 8 to 7, giving Θ(n^log₂7) ≈ Θ(n^2.81), a rare case of the leaf count itself being the thing to attack.

The finance-native divide-and-conquer problem is the maximum subarray: given a series of daily P&L, which contiguous stretch was best? Divide and conquer solves it in Θ(n log n), best in the left half, best in the right half, or best crossing the midpoint. Then Kadane's algorithm solves it in Θ(n) with one variable, by noticing that the best subarray ending at i either extends the best ending at i−1 or starts fresh. That is a dynamic program three sections early, and the lesson is that divide and conquer is a strong first answer a good linear insight sometimes beats. Its mirror image, the worst contiguous stretch, is the peak-to-trough of a drawdown, which is why CS1.05-e04's max_drawdown is a single pass and not a nested loop.

Greedy: when local really is global

A greedy algorithm takes the best-looking option at each step and never reconsiders. It is the fastest thing you can write and it is wrong more often than right, so the whole skill is knowing which it is this time, and that requires a proof, not a feeling.

The canonical correct case is interval scheduling: from tasks with start and end times, select the largest non-overlapping set. The greedy rule is always take the task that finishes earliest among those still compatible, and it is optimal by an exchange argument: let G be greedy's solution and O any optimal one, both ordered by finish time. Greedy's first choice finishes no later than O's, so swapping O's first task for greedy's leaves a solution still feasible and the same size; induct, and after each swap the modified optimum agrees with greedy on one more task and never shrinks. That template (show any optimal solution can be transformed step by step into the greedy one without getting worse) is what a greedy correctness proof looks like, and if you cannot construct it, you do not have a greedy problem.

Two more that work: fractional knapsack (take items in descending value-per-unit-weight, splitting the last, a fair model for allocating capital across divisible positions under a size cap) and Huffman coding (repeatedly merge the two least-frequent symbols for the optimal prefix code, the compression under every columnar format in CS2.04).

And the one that fails, which you must be able to produce on demand. 0/1 knapsack (items indivisible) breaks greedy, and here is the counterexample to keep. Capacity 50; three projects with (value, cost): A = (60, 10), B = (100, 20), C = (120, 30), so the value-per-unit densities are 6.0, 5.0 and 4.0. Greedy by density takes A (10 spent, value 60), then B (30 spent, value 160), then cannot fit C in the remaining 20, and stops at 160. The optimum takes B and C, spending exactly 50 for 220. Greedy is short by 27%, and no tie-breaking rescues it: the densities are strictly ordered and greedy still loses, because indivisibility means the last unit of budget cannot be filled fractionally. The finance form is not academic, this is capital budgeting, where projects are all-or-nothing and the highest-NPV-per-rupee project can consume a budget that two slightly worse projects would have used better. The same failure explains why coin change is greedy-safe with the standard Indian (₹1/2/5/10/20) and US (1/5/10/25¢) denominations but unsafe in general: with denominations {1, 3, 4} and a target of 6, greedy takes 4 + 1 + 1 = three coins where 3 + 3 = two coins is optimal. When greedy fails, the successor is dynamic programming.

Dynamic programming: the two conditions

Dynamic programming applies when a problem has optimal substructure (an optimal solution is built from optimal solutions to subproblems) and overlapping subproblems (the same subproblem is solved many times). The first condition alone gives you divide and conquer; it is the second that makes DP a distinct technique, because it means you can store each subproblem's answer and pay for it once.

The canonical demonstration is Fibonacci: naive recursion is Θ(φⁿ) because fib(n−2) is recomputed exponentially often; memoise it and there are only n distinct subproblems at O(1) each, so it becomes Θ(n). That is the general cost formula, worth memorising as a sentence: the cost of a DP is (number of distinct states) × (cost of computing one state from its predecessors). Get those two numbers and you have the complexity before you write a line. Two implementation styles: top-down memoisation is easier to derive, computes only the states you need, and risks stack overflow at depth; bottom-up tabulation is faster, has no depth limit, and usually allows the key optimisation, if state i depends only on state i−1, throw the table away and keep two rows, dropping space from Θ(n) to Θ(1).

The finance-native example, and the crown exercise of this section, is best profit with at most k transactions. Prices for n days; at most k non-overlapping round trips; what is the maximum? Brute force over transaction boundaries is exponential. The DP carries two arrays indexed by trip count t = 0…k: hold[t], the best cash position while holding, having opened trip t, and free[t], the best while flat, having completed t trips. For each price p and each t: hold[t] = max(hold[t], free[t−1] − p) (open trip t by buying at p) and free[t] = max(free[t], hold[t] + p) (close it by selling at p). States number n·k at O(1) each, so Θ(n·k) time and Θ(k) space. That is CS1.05-e10, whose hidden tests check it against an exhaustive search on short tapes (a reference sharing no code with the DP) plus two closed forms: once k ≥ n/2 the constraint stops binding and the answer collapses to the sum of every positive day-over-day move, and the unlimited-trips-with-fee variant at fee zero must equal that same sum.

The same state machine covers the family, a cooldown day after each sale, a flat fee per trade (max_profit_with_fee, Θ(n) with two scalars), a shorting state, and DP's other finance appearances are everywhere: 0/1 knapsack as capital budgeting under a hard budget (Θ(n·W), and note that "polynomial in the numeric value of W" is pseudo-polynomial, not polynomial in the input length); edit distance for fuzzy security-name matching across vendor files (Θ(n·m)); longest increasing subsequence as the longest run of improving prices; and optimal execution scheduling, where the state is inventory remaining and time left (QD2.01).

Say the caveat out loud, because a crown node should: every one of these DPs assumes the future price path is known. They compute a perfect-hindsight upper bound, which is exactly what makes them useful as the denominator you measure a real strategy against, and exactly what makes them worthless as strategies. Confusing the two is the purest form of look-ahead bias, and QD1.03 will make you hunt it.

Choosing: the decision table and the interview bar

Everything above collapses into one habit: name the operation profile first, then pick the structure. What do you do most, insert, look up by key, query a range, take the minimum, iterate in order? What worst case must you survive, as opposed to the average you hope for? Does order matter? Does stability? How much memory can you spend?

The interview bar, and the desk bar, which is the same bar, is that you can say all of this out loud, unprompted, before you write code: restate the problem and its constraints; name the brute force and its complexity; identify the structure or paradigm that improves it and say why; state the target complexity and the trade you are making for it; write it; then walk the edge cases (empty, one element, all equal, sorted, reverse sorted, huge) and say what the code does on each. That sequence is not interview theatre, it is the same sequence that stops you shipping an O(n²) function into a nightly pipeline, and it is what this node is really training.

Common mistakes & how experts think differently

1. Quoting a complexity without naming the case. "Hash lookup is O(1)" and "quicksort is O(n log n)" are half-sentences. The expert says expected O(1) with worst case O(n), expected Θ(n log n) with worst case Θ(n²), and then asks what matters: can the bad case actually reach me here? In finance it usually can, because data arrives sorted by date and clustered by ticker, and sorted input is precisely what degenerates a naive BST and a first-element-pivot quicksort.

1. Treating amortised as average. Average-case is a claim about a distribution over inputs; amortised is a proven bound on any sequence, adversary included. The doubling array's O(1) append is amortised (every sequence of n appends costs under 3n, full stop) while a hash lookup's O(1) is expected and can be defeated by chosen keys. Experts reach for the accounting method (assign a credit, show it never goes negative) rather than hand-waving "it evens out".

1. Hidden quadratics inside innocent-looking code. list.pop(0) in a loop, s = s + chunk on strings, df = df.append(row), if x in some_list inside a loop over another list, re-sorting inside a loop. Each is one line and Θ(n) per iteration, making the loop Θ(n²). The expert's tell is the nesting of costs, not the nesting of for statements: read every line inside a loop and ask what that line costs.

1. Reaching for a fancy structure before checking n. A hash map has per-key overhead; a balanced tree has rotation and pointer costs; at n = 20 a linear scan of a contiguous list beats both comfortably. Experts ask "how big does this actually get?" before optimising, and know the answer flips: code that is right at n = 20 is indefensible at n = 20,000,000.

1. Optimising the wrong term. Shaving a 3× constant off a Θ(n²) inner loop that should have been Θ(n log n) is effort spent moving a wall three metres. Profile first, fix the dominant term, and (the harder discipline) accept a slower asymptotic when n is provably small and the code is clearer for it.

1. Confusing "the interpreter is slow" with "my algorithm is wrong". Time the job at two input sizes an order of magnitude apart: 10× input costing ~10× is a constant-factor problem (vectorise, better library, more cores); ~100× is a quadratic, and no hardware will save you. That single measurement is the most useful diagnostic in this node.

1. Believing recursion is free. Every call costs a stack frame and Python's default limit is around 1,000. A recursive tree walk is fine on a balanced million-node tree (height ~20) and blows up on a degenerate one built from sorted input. Experts either guarantee logarithmic depth or convert to an explicit stack, which is why CS1.05-e06's reference implementation is iterative throughout.

1. Ignoring stability when it is semantically load-bearing. Sorting fills by price with an unstable sort silently destroys time priority, a correctness bug producing plausible output and no error. Ask "do ties mean something here?" before choosing a sort, and remember that Python's sorted is stable, C's qsort is not, and "stable" is a promise to look up rather than assume.

1. Trusting a memorised answer over a derived one. Memorised complexity tables fail the moment the problem differs slightly from the one in the table. Experts re-derive from the structure (how tall is it, how many nodes at each height, how much work per node) and get the right answer for a problem they have never seen.

1. Accepting generated code that is plausibly shaped. Algorithmic code is where copilots are most fluent and most dangerous, because a subtly wrong boundary condition still produces correct output on the happy path. Hunt three failure modes specifically: an off-by-one at a binary-search or window boundary (right on the sample, wrong on the edge); a "clean" rewrite that swapped an O(1) operation for an O(n) one; and a hallucinated standard-library method. Read generated algorithmic code with a stopwatch and a stack of edge cases, not with gratitude: CS2.06 turns this into a full discipline.

The thread through all ten: an expert carries a cost model, not a list of facts. They re-derive bounds from a structure's shape, they know which of their bounds are guarantees and which are hopes, and they measure before they believe. That is why every exercise in CS1.05 is graded at a size where a wrong cost model simply fails to finish.

Worked examples

All monetary figures below are illustrative and synthetic unless traced to a named source (R3); the arithmetic is real and reproducible, the prices are not quotes.

Worked example 1: Amortised append, proven two ways, on a tick tape (US, $)

A capture process appends 1,000 trade prints from a US venue into a dynamic array that starts at capacity 1 and doubles when full. A reviewer objects: "some of those appends copy the whole array, you cannot call that O(1)." Settle it.

Solution. Step 1, the aggregate method. A resize fires exactly when the size reaches the current capacity, so with capacity starting at 1 the copies happen at sizes 1, 2, 4, 8, …, 512, and the array ends at capacity 1,024. Total elements copied = 1 + 2 + 4 + ⋯ + 512 = 1,023. Add the 1,000 single-slot writes: total work is 2,023 units for 1,000 appends, i.e. 2.023 per append. In general the geometric series 1 + 2 + ⋯ + 2^k is strictly less than 2^(k+1) ≤ 2n, so total work is under 3n and the amortised cost per append is O(1).

Step 2, the accounting method, which explains why. Charge every append 3 units. One pays for the write; two are banked as credit on that element. When an array of capacity c fills, the c/2 elements added since the previous resize each carry 2 banked units, exactly c units, exactly the c copies the resize performs. After 1,000 appends we have charged 3,000 and spent 2,023, leaving a balance of 977 ≥ 0. Because the balance is never negative, 3 units per append is a genuine upper bound.

Step 3: what breaks it. Grow by a fixed 1,000 slots instead and the copies become 1,000 + 2,000 + 3,000 + ⋯, an arithmetic series summing to Θ(n²/2). At n = 10⁶ that is ~5 × 10¹¹ element copies against doubling's ~2 × 10⁶, a factor of 250,000. Growth must be multiplicative.

Read it. The reviewer is right about the individual operation and wrong about the aggregate. Amortised is not "average over a distribution"; it is a proof about every possible sequence, which is why CS1.05-e01's hidden test asserts the exact capacity ladder (1, 2, 4, 4, 8, 8, 8, 8, 16, …) rather than merely checking that the values come back correctly. A grow-by-one array returns every value correctly and is quadratic.

Worked example 2: A hash map by hand, including the resize (India, ₹)

A position blotter keys NSE symbols to holdings in ₹ lakh. The table starts with 8 buckets and resizes when the load factor exceeds 0.75. To make the arithmetic reproducible we use a deliberately simple teaching hash (the sum of the character codes) since Python's real hash() is randomly seeded per process and would give different buckets on every run.

Solution. Step 1: place the first six keys. Character-code sums and their bucket sum % 8:

Six keys, eight buckets: α = 6/8 = 0.75, which is not greater than 0.75, so no resize. Buckets 5 and 7 are empty; every chain has length 1.

Step 2, the seventh key collides and triggers the resize. WIPRO has Σ ord = 401, and 401 % 8 = 1, the bucket HDFCBANK already occupies. Chaining handles it: the pair is appended to that bucket's list, which now has length 2, and a lookup for WIPRO costs one hash plus two comparisons. But the insert takes α to 7/8 = 0.875 > 0.75, so the table doubles to 16 buckets and every entry is re-inserted at Σ ord % 16.

Step 3: recompute, and notice what moves. ITC 224 → 0 (unchanged), HDFCBANK 561 → 1, RELIANCE 579 → 3, INFY 310 → 6, but TCS 234 → 10 and SBIN 300 → 12. Changing the modulus scatters roughly half the keys, which is exactly why a resize is a rehash and not a memcpy, and exactly the step a rushed implementation forgets. The new load factor is 7/16 = 0.4375.

Step 4, the collision that survives. WIPRO 401 % 16 = 1, and HDFCBANK 561 % 16 = 1 too, because 561 − 401 = 160 is a multiple of 16. Doubling did not separate them, the honest statement of the hash guarantee is that resizing bounds the expected chain length at α, not that any particular pair will separate. Expected lookup cost is Θ(1 + α); with α under 0.75 that is a small constant, expected, never worst case.

Read it. Two habits fall out: re-derive the bucket index after the modulus changes, always; and when someone says a dictionary lookup is O(1), hear the missing word: expected. CS1.05-e02 pins the resize ladder exactly because a map that never grows passes every correctness test and then quietly becomes a linear scan on real data.

Worked example 3: The monotonic deque, traced and proven (US, $)

Ten daily closes for a US large-cap (illustrative, $): 412.00, 418.50, 415.00, 421.00, 409.50, 407.00, 424.00, 419.50, 431.00, 428.50. Compute the 4-day rolling maximum and prove the method is linear.

Solution. Step 1, the answer, and the naive cost. The seven windows give [421.00, 421.00, 421.00, 424.00, 424.00, 431.00, 431.00]. Computing them as max(prices[i:i+4]) costs 7 × 4 = 28 comparisons here, and Θ(n·w) in general.

Step 2, trace the deque of indices (prices strictly decreasing front to back).

Ten pushes, eight pops: 18 operations against the naive 28, and the gap widens without limit as w grows.

Step 3, the proof that the inner while is not a second loop. Each index is appended exactly once and removed at most once (from the back as dominated, or from the front as expired). Therefore across the entire run the total number of pops is at most n, and total work is at most 2n operations: Θ(n), independent of w. This is an amortised argument in miniature, the individual step can cost O(w), the sequence cannot.

Step 4, the scale that makes it matter. At n = 300,000 and w = 5,000 the naive form performs 295,001 × 5,000 = 1.475 × 10⁹ comparisons; the deque performs at most 600,000 operations, about 2,458× less work. CS1.05-e04 runs exactly those sizes: a correct O(n) answer finishes in well under a second and an O(n·w) answer never finishes at all.

Read it. The invariant is the whole idea, so say it out loud before coding: a price smaller than a later price can never again be a window maximum, so discard it the moment that later price arrives. Every monotonic-stack problem (next greater element, largest rectangle in a histogram, longest time since the last new high) is that one sentence re-dressed.

Worked example 4: Floyd's heap build and top-k, by hand (India, ₹)

Seven positions with values in ₹ crore: [92, 41, 73, 15, 26, 88, 64], arranged as the array [92, 41, 73, 15, 88, 26, 64]. Build a min-heap in place, then find the three largest positions.

Solution. Step 1. Floyd's bottom-up build. Internal nodes run from index n//2 − 1 = 2 down to 0; leaves need nothing because a leaf trivially satisfies the heap property.

• i = 2 (value 73; children 26 at index 5 and 64 at index 6). Smallest of {73, 26, 64} is 26 → swap. Array: [92, 41, 26, 15, 88, 73, 64].
• i = 1 (value 41; children 15 at index 3 and 88 at index 4). Smallest is 15 → swap. Array: [92, 15, 26, 41, 88, 73, 64].
• i = 0 (value 92; children 15 and 26). Smallest is 15 → swap, then continue from index 1 (value 92; children 41 and 88) → swap with 41. Array: [15, 41, 26, 92, 88, 73, 64].

Check the invariant: 15 ≤ {41, 26}; 41 ≤ {92, 88}; 26 ≤ {73, 64}. Valid, and the minimum is at the root. Four swaps total.

Step 2, the O(n) proof, checked against those four swaps. In this tree there are 4 nodes at height 0, 2 at height 1, and 1 at height 2. Sift-down at a node of height h costs at most h swaps, so the total is at most 4·0 + 2·1 + 1·2 = 4, precisely what we observed. In general the count of nodes at height h is at most ⌈n/2^(h+1)⌉, so the total is O(n · Σ_{h≥0} h/2^h) = O(2n) = Θ(n), because Σ h/2^h converges to 2. Sanity-check the size of that win on a perfect tree of n = 1,023: the sum Σ 2^(9−h)·h over h = 0…9 is 1,013 swaps, against the push-by-push build's ≈ n log₂ n = 10,230, a 10× saving that grows with n.

Step 3: top-3 with a bounded min-heap. Push the first three values (92, 41, 73) to get a heap whose root is 41, the weakest survivor. Then: 15 > 41? No, discard. 88 > 41? Yes, pop 41, push 88; the root becomes 73. 26 > 73? No. 64 > 73? No. The heap holds {73, 88, 92}; drained and reversed that is [92, 88, 73] ✓.

Step 4, why not just sort? At n = 400,000 and k = 10, sorting is ≈ n log₂n = 7.44 × 10⁶ comparisons and Θ(n) extra space; the bounded heap is ≈ n log₂k = 1.33 × 10⁶ comparisons and 10 slots, roughly 5.6× less work and 40,000× less memory.

Read it. Two counter-intuitive moves earn their keep: a min-heap finds maxima (the thing you must cheaply identify is the weakest item you would evict), and Floyd's build is asymptotically free relative to the pops that follow. CS1.05-e05 asserts the exact array layout because a sorted list also satisfies the heap property, and we want the structure, not a lookalike.

Worked example 5: Merge sort: the recurrence, and why stability is a correctness property (US, $)

Five fills arrive in this order, each (price, id): (101.50, F1), (100.25, F2), (101.50, F3), (100.25, F4), (101.50, F5). Sort them by price ascending and count the inversions, then say what an unstable sort would have done.

Solution. Step 1, the stable result. Sorting by price only, taking from the left half on ties, gives F2, F4, F1, F3, F5: the two 100.25 fills in arrival order, then the three 101.50 fills in arrival order. Inversions = 3, the pairs (F1, F2), (F1, F4) and (F3, F4), each a higher price arriving before a lower one.

Step 2, why an unstable sort is a bug, not a preference. Exchanges match on price-time priority. Among equal prices the earlier order has the senior claim. An unstable sort may emit F5, F3, F1 within the 101.50 group, a legal permutation by price and a false statement about queue position. Nothing errors; the output looks fine; the downstream fill allocation is wrong. Merge sort is stable precisely when the merge takes from the left half on ties, which is why CS1.05-e07 specifies a strict < comparison against the right half.

Step 3: solve the recurrence twice. Merge sort splits in half, recurses, and merges linearly: T(n) = 2·T(n/2) + Θ(n). By recursion tree: every level performs Θ(n) merge work and the halving gives log₂ n levels, so Θ(n log n). At n = 1,048,576 = 2²⁰ that is 20 levels × n = 2.1 × 10⁷ merge steps. By the master theorem: a = 2, b = 2, f(n) = Θ(n), and n^(log_b a) = n^(log₂2) = n¹ = f(n), so case 2 applies and T(n) = Θ(n^(log_b a) · log n) = Θ(n log n). Both routes agree, in every case, worst, average and best, which is the guarantee quicksort cannot make.

Step 4, the free statistic. Each time the merge takes an element from the right half, every element still remaining in the left half is inverted against it, so adding len(left) − i counts inversions at zero asymptotic cost. Counting them separately is Θ(n²): at n = 100,000 that is 5 × 10⁹ comparisons, which is why CS1.05-e07 grades at that size and uses closed forms, a reversed array of n distinct keys has exactly n(n−1)/2 inversions, and two swapped blocks of sizes a and b have exactly a·b, that sorted() cannot produce.

Read it. "Is the sort stable?" is a question about meaning, not about performance, and it is the kind of defect that ships. Python's sorted and list.sort are stable (Timsort); C's qsort and most naive quicksorts are not. Look it up rather than assume it.

Worked example 6: Triangular arbitrage is a negative cycle (India ₹ / US $ / EUR)

Three illustrative quotes: USD → INR 83.20, INR → EUR 0.01110, EUR → USD 1.0870. Is there an arbitrage, and how does a shortest-path algorithm find it?

Solution. Step 1, the direct check. Start with $1. It buys ₹83.20, which buys €0.923520, which buys $1.003866. The cycle multiplies to 1.003866, a gross gain of 0.3866% per round trip.

Step 2, the transform that makes it a graph problem. Conversion multiplies; shortest-path algorithms add. Set each edge weight to w = −ln r:

• USD → INR: −ln 83.20 = −4.421247
• INR → EUR: −ln 0.01110 = +4.500812
• EUR → USD: −ln 1.0870 = −0.083424

The cycle sum is −0.003859. Since Π rᵢ > 1 ⟺ Σ (−ln rᵢ) < 0, arbitrage is exactly a negative cycle, and −ln(1.003866) = −0.003859 confirms the identity numerically. Recover the gain as e^0.003859 − 1 = 0.3866%.

Step 3: how Bellman-Ford finds it. Initialise every distance to 0.0, equivalent to a virtual source with a free edge to each currency, which is what lets the search find a negative cycle anywhere rather than only one reachable from a chosen start. Relax all edges V − 1 = 2 times (a shortest simple path visits at most V vertices and so uses at most V − 1 edges, so V − 1 passes suffice for convergence when no negative cycle exists). Then sweep once more: any edge that still relaxes proves some path is improving without bound, which only a negative cycle allows. With V = 6 currencies fully cross-quoted the cost is V − 1 = 5 passes plus one detection sweep over E = 30 edges: 180 relaxations, i.e. O(V·E).

Step 4, the tolerance is not decoration. Quote EUR → USD at 1.082814 instead and the triangle multiplies to exactly 1.000000: no arbitrage. A consistent quote matrix built from ratios of the same underlying values produces cycle sums of ±10⁻¹⁵ from floating-point rounding alone, so a detector with no tolerance fires on every book it sees. Compare with dist[a] + w < dist[b] − ε for a small ε (10⁻⁹ in CS1.05-e09) and the noise is filtered while a real 20 bp mis-quote is still caught.

Step 5, the honesty check. The 0.3866% is gross, on mid quotes. Charge a realistic 5 bp half-spread per leg and three legs cost ≈ 0.15%, leaving ≈ 0.24%. At 15 bp per leg the cost is 0.45% and the opportunity is gone, before you add latency, minimum ticket sizes and the near-certainty that a stale quote is stale for a reason. The algorithm answers "is there a negative cycle in these numbers"; whether it is money is a different question, asked properly in QD2.01.

Read it. The transferable move is the transform: when the combining operation is multiplication and your tool set is additive, take logarithms. The same trick converts compounding returns into summable log-returns (QM1.01) and products of likelihoods into summable log-likelihoods.

Worked example 7: Best profit with at most k trades, tabulated (India, ₹)

Eight daily closes for an NSE-listed name (illustrative, ₹): 1240, 1215, 1288, 1262, 1201, 1259, 1233, 1301. With perfect hindsight, what is the most you could have made with at most two round trips? Show the state machine.

Solution. Step 1: set up the states. Carry two arrays indexed by trip count t = 0…2. hold[t] is the best cash position while holding, having opened trip t; free[t] is the best while flat, having completed t trips. Initialise hold = [−∞, −∞, −∞] and free = [0, 0, 0]. For each price p and each t = 1…k: hold[t] = max(hold[t], free[t−1] − p) (buy at p, opening trip t) and free[t] = max(free[t], hold[t] + p) (sell at p, closing it).

Step 2: walk the tape.

Step 3, read and check the answer. free[2] = ₹173 per share. Decompose it: buy at 1215, sell at 1288 (+73), then buy at 1201 and hold through the 1233 dip to sell at 1301 (+100). The single-trip answer is free[1] = ₹100 (buy 1201, sell 1301), and with three or more trips the answer rises to ₹199, which equals the sum of every positive day-over-day move (73 + 58 + 68), because once k ≥ ⌊n/2⌋ the constraint stops binding. That closed form is an independent check on the whole table, and CS1.05-e10's hidden tests use it.

Step 4, the complexity, from the formula. Cost = (states) × (cost per state) = (n·k) × O(1) = Θ(n·k) time, and since each price row depends only on the previous one, Θ(k) space, for a year of daily data with k = 5, that is 1,260 states and six slots. Note also that the DP found a solution (holding through the day-7 dip) that a "take every up-move" heuristic would have split into two trips it did not have.

Read it, and read the caveat. This computes a perfect-hindsight upper bound: the honest denominator against which a real strategy's return should be measured, and worthless as a strategy, because it uses tomorrow's prices today. Confusing the two is the purest form of look-ahead bias: QD1.03 will make you hunt it, and QD2.05 will fail a capstone that hides it.

Worked example 8: Binary search on the answer: yield to maturity by bisection (US, $)

An illustrative US Treasury-style bond: face $1,000, 5% annual coupon paid semiannually ($25 per period), 10 years (20 periods), quoted at $925.61. Find the yield, and say in advance how many iterations it will take.

Solution. Step 1, establish monotonicity, which is what licenses binary search. Price is the sum of discounted cash flows, and every term is strictly decreasing in the yield, so price is strictly decreasing in yield. A strictly monotone function has at most one root, so the bisection invariant the answer lies inside [lo, hi] can be maintained by discarding whichever half cannot contain it.

Step 2, the iteration count, before running anything. Each step halves the bracket, so from an initial width W the bracket after k steps is W/2^k. To reach a tolerance ε you need k = ⌈log₂(W/ε)⌉. Bracketing the annual yield in [0%, 20%] (W = 0.20) to ε = 10⁻⁶ (0.01 bp) requires ⌈log₂(200,000)⌉ = ⌈17.61⌉ = 18 iterations, after which the bracket is 7.63 × 10⁻⁷, inside tolerance. Note what this bound does not depend on: the shape of the function, the starting guess, or the data. That is bisection's whole selling point.

Step 3, the first three steps.

(Step 2 lands exactly on par, as it must: a 5% coupon priced at a 5% yield is worth face value.) Continuing converges on 6.00% nominal annual (3.00% semiannual), which reprices the bond at $925.61 ✓.

Step 4, when to use something else. Newton-Raphson converges quadratically, roughly doubling the correct digits each step, so ~4 iterations here instead of 18, but it needs a derivative and can diverge on a badly behaved function. Bisection needs only a sign change and cannot fail while the function is continuous. For an IRR on a stream with multiple sign changes, "slower and cannot fail" is the correct engineering choice; the standard professional answer is a hybrid (Brent's method) that takes fast steps when they behave and falls back to bisection when they do not.

Read it. Generalise the move: binary search is not an array technique, it is a monotonicity technique. Anywhere a scalar answer makes a predicate flip from false to true exactly once, implied volatility from an option price, the break-even discount rate, the smallest position size that breaches a risk limit, you can bisect, and state the iteration count before you start.

Practice set

Work each problem fully before reading its solution. Numeric answers are to about ±2%. All figures are illustrative unless traced to a source.

P1 (guided). Total copies under doubling. A dynamic array starts at capacity 1 and doubles when full. After 1,000 appends, how many element copies have been performed, what is the final capacity, and what is the total work per append?

Solution. Resizes fire at sizes 1, 2, 4, …, 512, copying 1 + 2 + 4 + ⋯ + 512 = 1,023 elements; the final capacity is 1,024. Total work = 1,000 writes + 1,023 copies = 2,023 units, about 2.02 per append, a constant, independent of n, because the geometric series 1 + 2 + ⋯ + 2^k < 2^(k+1) ≤ 2n.

P2 (guided). Resize ladder and rehash volume. A hash map starts with 16 buckets and doubles when the load factor exceeds 0.75. You insert 200 distinct keys. How many resizes occur, at which key counts, what is the final bucket count and load factor, and how many entries are re-inserted in total?

Solution. A resize fires at the first n with n/m > 0.75. From m = 16: n = 13 (→32), then 25 (→64), then 49 (→128), then 97 (→256), then 193 (→512): five resizes. Final bucket count 512, α = 200/512 = 0.391. Entries rehashed = 13 + 25 + 49 + 97 + 193 = 377, comfortably under 2n = 400, which is the doubling argument again: rehashing is Θ(n) each time but rare enough to be O(1) amortised.

P3. Ring-buffer arithmetic. A ring queue has capacity 8, head = 6 and size = 5. At which index does the next enqueue write? After three dequeues, what are head and size?

Solution. enqueue writes at (head + size) % capacity = (6 + 5) % 8 = 11 % 8 = index 3, the buffer has wrapped. After three dequeues, head = (6 + 3) % 8 = 1 and size = 2. Nothing shifted: both operations are O(1) worst case, against list.pop(0)'s Θ(n).

P4. Prove the deque window is linear. A while loop sits inside a for loop in the monotonic-deque rolling maximum, which looks quadratic. Prove it is Θ(n), then quantify the saving at n = 300,000 and w = 5,000.

Solution. Each index is appended exactly once and removed at most once (from the back when dominated, or from the front when it expires), so the total number of pops across the whole run is at most n. Total work ≤ 2n operations. Θ(n), independent of w. At the stated sizes: naive = (300,000 − 5,000 + 1) × 5,000 = 1.475 × 10⁹ comparisons versus at most 600,000 deque operations, a factor of about 2,458.

P5. Three BST heights. For n = 1,048,575 keys, give the minimum possible height, the maximum possible height and the height you should expect from randomly ordered inserts (heights in edges). Which order produces the maximum, and why does it matter in finance?

Solution. n = 2²⁰ − 1, so a perfectly balanced tree has height 19 (a tree of height h holds at most 2^(h+1) − 1 nodes). The maximum is n − 1 = 1,048,574, produced by inserting the keys in sorted order, each new key becomes the right child of the last and the tree is a linked list. Random insertion order gives expected height ≈ 4.31 ln n ≈ 60. It matters because financial data arrives sorted by date essentially always, so the worst case is the default case unless you balance or shuffle.

P6. Floyd's build, counted. For a perfect min-heap of n = 1,023, bound the total number of swaps in Floyd's bottom-up build using the nodes-at-height-h argument, and compare with the push-by-push build.

Solution. A perfect tree of 1,023 nodes has height 9, with 2^(9−h) nodes at height h. Sift-down at height h costs at most h swaps, so the total is Σ_{h=0}^{9} 2^(9−h)·h = 256 + 256 + 192 + 128 + 80 + 48 + 28 + 16 + 9 = 1,013 swaps: fewer than n. The push-based build is n log₂ n ≈ 10,230, about 10× more. The general bound is O(n · Σ h/2^h) = O(2n) = Θ(n), since Σ_{h≥0} h/2^h = 2.

P7. Top-k: heap versus sort. From 400,000 position values you need the 10 largest. Compare a full sort against a bounded min-heap on both time and auxiliary space, with numbers.

Solution. Sorting: Θ(n log n) ≈ 400,000 × 18.61 = 7.44 × 10⁶ comparisons and Θ(n) auxiliary space. Bounded min-heap of size k: Θ(n log k) ≈ 400,000 × 3.32 = 1.33 × 10⁶ comparisons and Θ(k) = 10 slots. About 5.6× less work and four orders of magnitude less memory. The trick is that a min-heap of size k keeps the weakest survivor at the root, so each candidate is admitted or rejected in one O(1) comparison.

P8. The comparison lower bound. Prove that any comparison-based sort needs Ω(n log n) comparisons in the worst case, and evaluate the bound for n = 20.

Solution. Model the algorithm as a binary decision tree: internal nodes are comparisons, leaves are output permutations. Correctness requires that all n! permutations be reachable, so there are ≥ n! leaves; a binary tree with L leaves has height ≥ log₂ L; and the worst-case comparison count is the height. Hence comparisons ≥ log₂(n!) = Θ(n log n) by Stirling. For n = 20: log₂(20!) = 61.08, so at least 62 comparisons are needed in the worst case (Stirling's approximation gives 61.07: agreement to two decimals). Merge sort and heapsort are therefore asymptotically optimal, and the linear-time sorts (counting, radix) escape the bound only by not comparing.

P9. Stability as correctness. Three fills arrive at the same price, in order F1, F2, F3, and you re-sort the tape by price with an unstable sort. What can go wrong, why does nothing error, and which common sorts are stable?

Solution. An unstable sort may emit them as F3, F1, F2, a legal ordering by price and a false statement about time priority, which is the tie-break exchanges actually match on. Nothing errors because the output is a valid permutation with correct prices; the defect is semantic and silently propagates into fill allocation. Stable: merge sort (taking from the left half on ties), insertion sort, counting/radix sort, and Python's Timsort (sorted, list.sort). Not stable: heapsort, and quicksort as normally written. When ties carry meaning, verify stability from the documentation rather than assuming it.

P10. Kahn's algorithm reports 37 of 40. A model has 40 cells; your topological sort emits 37 and then finds nothing ready. What has happened, what should the function return, and what is the cost of that check?

Solution. The three unemitted cells never reached in-degree zero, which means each is waiting on another cell inside the same group, a cycle, i.e. a circular reference. The function must return failure (None), not the partial order, because a partial order is a plausible-looking answer to a model that has no valid evaluation order at all. The cost of detecting it is a single length comparison at the end: cycle detection in Kahn's algorithm is free, which is the main reason to prefer it over a DFS-based topological sort when "is this circular?" matters as much as the order.

P11. Bellman-Ford on a currency book. With V = 6 currencies fully cross-quoted (E = 30 directed edges), how many relaxation passes are needed and why? Convert the quotes USD→INR 83.20, INR→EUR 0.01110, EUR→USD 1.0870 into edge weights and state the verdict.

Solution. V − 1 = 5 passes, because a shortest simple path visits at most V vertices and therefore uses at most V − 1 edges, five passes suffice for convergence when no negative cycle exists. Then one more detection sweep: any edge that still relaxes proves a path improving without bound, i.e. a negative cycle. Total ≈ 6 × 30 = 180 relaxations, O(V·E). Weights w = −ln r: −4.421247, +4.500812, −0.083424, summing to −0.003859 < 0, a negative cycle, so arbitrage exists, worth e^0.003859 − 1 = 0.387% gross per round trip before spreads.

P12. Greedy fails 0/1 knapsack. Capacity 50; projects A = (value 60, cost 10), B = (100, 20), C = (120, 30). Compute the greedy-by-density answer and the true optimum, and name the finance situation this is.

Solution. Densities are 6.0, 5.0, 4.0. Greedy takes A (spend 10, value 60), then B (spend 30, value 160), then cannot fit C in the remaining 20 → 160. The optimum takes B + C: cost exactly 50, value 220. Greedy is short by 60, or 27%. This is capital budgeting with indivisible projects: the best NPV-per-rupee project can consume budget that two slightly worse projects would have used better. Fractional knapsack (divisible positions) is greedy-optimal; 0/1 is not, and its correct treatment is dynamic programming at Θ(n·W).

P13. Size the DP. For max_profit_k over 252 trading days with k = 5, give the number of states, the time and space complexity, and the value of k beyond which the answer stops changing.

Solution. States = n × k = 252 × 5 = 1,260, each computed in O(1) from its predecessors, so Θ(n·k) time. Each price row depends only on the previous one, so two rolling arrays of length k + 1 suffice: Θ(k) space (six slots here). The answer stops changing once k ≥ ⌊n/2⌋ = 126, because at most ⌊n/2⌋ non-overlapping round trips exist; beyond that the answer equals the sum of every positive day-over-day move.

P14. Bisection iteration count. You solve for a yield by bisection with an initial bracket of [0%, 25%] and a tolerance of 0.5 bp. How many iterations, and what does the answer depend on?

Solution. W = 0.25 and ε = 5 × 10⁻⁵, so k = ⌈log₂(W/ε)⌉ = ⌈log₂ 5,000⌉ = ⌈12.29⌉ = 13 iterations. It depends only on the bracket width and the tolerance, not on the function, the data, or the starting guess. That predictability is exactly what you trade away by switching to Newton-Raphson, which is faster (quadratic convergence) but can diverge; the professional compromise is a hybrid such as Brent's method.

P15. Diagnose the wall. A nightly job takes 4.2 s on 100,000 rows and 415 s on 1,000,000 rows. Diagnose it, and say what would and would not help.

Solution. A 10× input produced a 98.8× slowdown, very close to 100×, the signature of a quadratic algorithm (10× input on a linear job costs ~10×; on an n log n job ~11.7×). Faster hardware, more cores, or a compiled rewrite move a Θ(n²) wall by a constant factor and leave it a wall; at 10⁷ rows the job would take about 11.5 hours. What helps is finding the nested cost, a linear operation inside a loop (list.pop(0), x in some_list, string concatenation, df.append), an unpruned scan inside a per-row query, or a genuine double loop, and replacing it with a hash lookup, a queue with a head pointer, or a single pass. Time at two sizes an order of magnitude apart before you optimise anything: that one measurement distinguishes a constant-factor problem from an algorithmic one, and they have completely different fixes.

Applied mini-project

Build a limit order book, and then prove its complexity.

This project composes the whole node. A limit order book is not one data structure but three, chosen for three different access patterns and glued together, the single best artefact for demonstrating that you can pick structures on purpose. You will build it, benchmark it, then deliberately break it to show what the wrong choice costs.

The design (decide this before you write a line, and write the decision down).

• Price levels need order. You must find the best bid (highest) and best ask (lowest) and walk outward for depth, an ordered structure: a balanced tree, or a sorted structure over price levels whose cost you can state honestly.
• Orders within a level need time priority. First in, first out, with O(1) removal from the front, a queue: your ring buffer from CS1.05-e03, or a doubly linked list if you want O(1) cancellation from the middle.
• Cancellation needs point lookup. A cancel arrives with an order id, not a price. Scanning for it is O(n); a hash map from order id to location makes it O(1). This is the choice that separates a toy from a book.

Required operations. add_limit(order_id, side, price, qty); cancel(order_id); market_order(side, qty), match against the best price, exhausting each level in time-priority order and returning fills as (price, qty); best_bid() / best_ask(); depth(n). Handle partial fills, a market order that walks several levels, and one larger than the entire book.

Do this, in order.

1. State the target complexity for every operation before implementing, in a table, with the structure that delivers it. You are graded on this table being right, not ambitious.
2. Implement, reusing your own pack code (CS1.05-e02 hash map, CS1.05-e03 ring queue, CS1.05-e06 tree).
3. Test the semantics. Price-time priority must never break: at the same price, the earlier order fills first. Write the test that would catch a violation.
4. Benchmark. Time each operation at 10³, 10⁴ and 10⁵ resting orders, reporting time per operation. Flat per-operation cost is O(1); growth by a constant per 10× is O(log n); 10× per 10× is O(n).
5. Ablate, this is the part that teaches. Rerun with two deliberate downgrades: (a) the per-level FIFO replaced by list.pop(0), and (b) cancellation by linear scan instead of the id → location map. Report the slowdown at each size and identify which curve changed shape rather than merely shifting.
6. Write the memo. One page: the design table (claimed complexity, structure, measured scaling), the ablation results, and one paragraph on the largest gap between claim and measurement with a hypothesis for it. Cache effects, allocation overhead and the interpreter constant are all legitimate explanations, naming one correctly scores better than a measurement that happens to match.

Deliverable. One module plus one page. The module exposes the six operations and passes your own price-time-priority tests; the memo carries the complexity table, the three benchmark curves, the ablation, and the discrepancy paragraph.

Rubric (100 points; pass at ≥ 80 with no zero on any line, this is a crown node).

Self-check before you submit. Can you say out loud, in under sixty seconds: what each structure is, what it costs, what it would cost if you had chosen the obvious alternative, and which single operation would be the first to hurt at ten times the size? That sixty seconds is the interview, and the desk conversation, and the reason this node exists.

{
  "skill": "Benchmarking and reviewing algorithmic code — yours or a copilot's — for the complexity it actually has rather than the one it claims",
  "use": "After your order book runs, use an assistant to draft the benchmark harness (timing loops, warm-up, size sweep, tabulated output) and to red-team your complexity table: ask it to argue that each of your claimed bounds is wrong and to name the input that would prove it. You do the measuring; it does the adversarial thinking. Generate in your own tool, paste the code back here, and let this node's tests and your own timings judge it.",
  "tools": ["Chat assistants — Claude, ChatGPT, Gemini", "IDE copilots — GitHub Copilot, Cursor", "Standard-library profilers you run yourself — timeit, cProfile"],
  "prompt": "Here is my implementation of <OPERATION> and my claim that it is <COMPLEXITY>. (1) Argue the claim is wrong: name the specific input pattern or code path that would make it slower, and say what complexity it would actually be. (2) Write a timing harness that sweeps input size over three orders of magnitude and prints time PER OPERATION so the shape is visible. (3) List every hidden linear-cost operation in my code (indexing into a list by search, pop(0), `in` on a list, slicing inside a loop, re-sorting, string concatenation).",
  "verify": "Believe the stopwatch, not the model and not yourself: run the sweep and check the shape (10x input costing ~10x is linear, ~100x is quadratic, ~11.7x is n log n). Re-read every generated line for the three classic copilot failures on algorithmic code — an off-by-one at a window or bracket boundary that is correct on the sample, a 'cleaner' rewrite that silently swapped an O(1) operation for an O(n) one, and an invented standard-library method. Check every API against the real documentation (Primary-Source Guardrail: Trace, Recompute).",
  "diy": "Gated: you must have written your own complexity table BEFORE asking, and passed CS1.05-e01 through e07 by hand. A red-team of a claim you cannot defend is just a second opinion you cannot evaluate.",
  "market": "US"
}

Reading & resources

Everything below is an anchor to learn from and verify against, never a source to quote a number from without re-deriving it (R3). Tags: ✓ free / $ paid, and ▲ beginner–intermediate / ▼ advanced.

The core spine (pick one and go through it properly):

• Sedgewick & Wayne, Algorithms (4th ed.), the clearest treatment of the structures in this node, with the algs4 booksite and two Coursera courses free alongside the paid book. Start here if you want to build. [$ book / ✓ booksite + courses] [▲]
• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS), the standard reference and the source of the amortised-analysis, master-theorem and decision-tree treatments used above. Read it as a reference, not front to back. [$] [▼]
• Roughgarden, Algorithms Illuminated (four short volumes), Stanford lecture videos free, the best explanations of divide-and-conquer analysis and the greedy exchange argument. [$ books / ✓ lectures] [▲–▼]
• Skiena, The Algorithm Design Manual: war stories plus a catalogue of which algorithm solves which real problem; the most useful book here for choosing. [$] [▼]
• MIT OpenCourseWare 6.006 and 6.046: full lecture videos, notes and problem sets. [✓] [▼]

The primary literature (the results you proved above have authors):

• Floyd, "Algorithm 245: Treesort 3" (CACM, 1964), the bottom-up O(n) heap construction; and Williams, "Algorithm 232: Heapsort" (CACM, 1964), the heap itself. [$/library] [▼]
• Hoare, "Algorithm 64: Quicksort" (CACM, 1961) and "Quicksort" (Computer Journal, 1962). [$/library] [▼]
• Bellman, "On a Routing Problem" (1958) and Dijkstra, "A Note on Two Problems in Connexion with Graphs" (Numerische Mathematik, 1959), including the negative-cycle machinery behind the arbitrage detector. [$/library] [▼]
• Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm" (JACM, 1975), the inverse-Ackermann bound on union-find. [$/library] [▼]
• Bayer & McCreight, "Organization and Maintenance of Large Ordered Indices" (1972). B-trees, i.e. every database index you meet in CS2.03. [$/library] [▼]

Python-specific, worth an hour each:

• The Python wiki "TimeComplexity" page, official per-operation costs of list, dict, set, deque. The single most useful page in this bibliography. [✓] [▲]
• The collections.deque, heapq and bisect documentation, the production versions of three structures you just built. Build first, then read. [✓] [▲]
• CPython's Objects/listobject.c (the growth pattern) and Objects/dictobject.c with dictnotes.txt (open addressing, and why dict has preserved insertion order since 3.7). [✓] [▼]

Practice, and how to use it:

• visualgo.net: animated insert/delete on BSTs, AVL trees, heaps and graphs. Ten minutes here beats an hour of prose when a structure will not click. [✓] [▲]
• LeetCode / the NeetCode 150 roadmap, the drill ground for the interview bar. Use it after this node, and correctly: solve, re-derive the complexity, read the editorial, re-solve from scratch a week later. Skipping steps two and four builds recall, not skill. [✓ free tier / $] [▲–▼]
• Bentley, Programming Pearls: short essays on exactly the "this job got slow" diagnosis taught above. [$] [▲]

The finance bridge:

• Harris, Trading and Exchanges: Market Microstructure for Practitioners, the order book as an institution, which is what the mini-project models as a data structure. Cross-reference QD2.01. [$] [▼]
• Your own CS1.05 code pack: ten exercises whose hidden tests grade at sizes where the wrong complexity cannot finish. The only resource here that answers back.

Do this, not just read: open the Python TimeComplexity page and, for each of list, dict and deque, find one operation whose cost surprises you; then write a five-line script that times it at n = 10³ and n = 10⁵ and confirms the shape. Twenty minutes of that will change how you write loops permanently.

{
  "skill": "Drilling interview-standard DS&A with spaced, adversarial practice instead of passive rereading",
  "use": "Use an assistant as an infinite supply of variations and a Socratic examiner: have it restate a problem you just solved with a changed constraint (duplicates allowed, streaming input, memory-bounded, must be stable), demand your complexity claim before it comments, and make it ask you the follow-up an interviewer would. It generates the questions; the code pack grades the code.",
  "tools": ["Chat assistants — Claude, ChatGPT, Gemini", "Spaced-repetition tooling for this node's flashcard deck", "This node's code pack (CS1.05) as the grader — the app never calls a model at runtime"],
  "prompt": "I just solved <PROBLEM> in <COMPLEXITY>. Do NOT give me code. (1) Restate the problem with one constraint changed — duplicates allowed, input arrives as a stream, memory bounded to O(1), or the sort must be stable — and ask me which structure now applies. (2) Ask me for my complexity claim BEFORE you comment on it. (3) Then give me the follow-up an interviewer would ask, and one input on which a plausible-but-wrong solution silently returns the right answer.",
  "verify": "Take nothing on the model's word: re-derive every complexity claim from the structure (how tall is it, how many nodes at each height, how much work per node), and run your code against this node's hidden tests, which use closed-form invariants and sizes that a wrong-complexity answer cannot finish. Generated 'optimal' solutions are frequently one boundary condition wrong and occasionally cite a library function that does not exist — check both (Primary-Source Guardrail: Trace, Recompute).",
  "diy": "Gated: drill only what you can already derive. If you cannot state why a heap is O(log n) without looking it up, more problems will build pattern-matching on top of nothing — go back to the Core section and prove it first.",
  "market": "IN"
}

Teach it back & journal

Feynman prompt. Explain to a capable colleague who writes working Python but has never studied algorithms why their overnight job got 100× slower when the input got 10× bigger (using the sentence "a linear operation inside a loop is a quadratic algorithm") and then explain, without notation, why dict lookup is "fast" in a way that list search is not, and what dict gives up to be fast. Finish with the one structure they should reach for next time they write "find the top N of a very long list", and say what it costs. If they can, unprompted, spot a pop(0) in their own code and say why it is a bug rather than a style choice, and if they ask "but what if the data is already sorted?" about your binary search tree, you have installed the cost model, which is the whole point of this node.

Journal prompt. Take one script you have actually written (a backtest loop, a reconciliation, a data-cleaning pass) and audit it against this node. For every loop, name the cost of the most expensive operation inside it, and then state the loop's total complexity. Where is the dominant term? Time the script at two input sizes an order of magnitude apart and write down whether the shape you measured matches the shape you predicted; if it does not, that gap is the most valuable paragraph in this journal, so explain it rather than explaining it away. Then answer three questions in writing. Which single structure change would most improve that script, and what exactly would it cost you in code complexity? Which of your complexity claims are guarantees (amortised, worst case) and which are hopes (expected, average), and can the bad case actually reach you, given that financial data arrives sorted by date and clustered by symbol far more often than shuffled? And finally: over the next month, which is more likely to change how colleagues see your work, that you can write the algorithm, or that you can say what it will cost before you run it, and be right? Name the one habit from this node you will make automatic, and the next script you will apply it to.

This module's flashcards and mastery quiz are wired into the app: see the node's Quiz and Reviews.