Algorithmic Complexity
& Data Structures

Big-O is a statement about growth, not a stopwatch

Big-O describes how the work an algorithm does scales with the size of its input, ignoring constants. It answers one question: what breaks as n grows? It deliberately refuses to answer a different one: how many microseconds does this take on my laptop today.

Those are complementary. Big-O tells you which curve you are on; profiling tells you where you sit on it. You need both, and you need them in that order, because you cannot optimise your way out of the wrong curve. Complexity is a design decision made when you choose the container — not a tweak you apply afterwards.

The ladder below is the whole vocabulary. O(1) is a dict lookup or a deque append: it does not care about n. O(log n) is a binary search or a heap push — doubling n adds a single step. O(n) is scanning a list. O(n log n) is a sort, the realistic floor for comparison sorting. O(n²) is a nested loop over the data: perfectly fine at n = 100, and fatal at n = 10⁶.

Choosing the container is choosing the complexity

Know the cost of the operation you perform most often, then pick the structure that makes that one operation cheap. Everything else is negotiable.

The order book is a data-structure problem

An order book must answer “what is the best price?” constantly, and it must match by price–time priority: best price first, and within a price, earliest arrival first. Every design decision in shared/orderbook.py follows from those two sentences.

The naive answer is a list of resting orders that you scan to find the best bid and ask. That scan is O(n), and you do it on every single incoming order. Book depth is not small and it grows during exactly the volatile moments when you need speed most.

The arena's answer is a min-heap plus a dict. The heap gives O(log n) insert and O(1) peek at the extreme — exactly the operation repeated most. The heap is keyed on the tuple (price, seq, order_id): price orders the book, seq breaks ties by strict arrival order, and the id is the final tiebreak. It is seq and not a timestamp because floats tie and a monotonic counter never does — that is what makes time priority true rather than approximate.

The last trick is where students get surprised. A dict of live orders is the canonical source of truth; the heaps are only a fast index into it. Cancelling deletes from the dict and leaves the heap entry behind — lazy deletion — so cancels are O(1) and stale entries are discarded when they surface at the top. Reads iterate the canonical set, so a lazily-stale heap entry can never leak into an answer.

The other hot path: statistics that recompute themselves

on_tick fires on every price update. If it recomputes a mean and a volatility over the full window each time, the per-tick cost is O(k) and the session cost is O(n·k) — the classic O(n²) trap when the window is the whole history. The fix is to keep running state instead of rescanning: a running sum gives an O(1) mean, and Welford's method gives mean and variance in one pass, in constant time, without ever storing history.

# O(1) per tick, numerically stable
class Welford:
    def __init__(self):
        self.n=0; self.mean=0.0; self.m2=0.0
    def update(self, x):
        self.n += 1
        d = x - self.mean
        self.mean += d / self.n
        self.m2   += d * (x - self.mean)
    @property
    def var(self):
        return self.m2/(self.n-1) if self.n>1 else 0.0

Put the two together and on_tick becomes cheap and flat for the whole session. This is the pattern to copy into your bot this week:

class MyBot(Trader):
    def __init__(self):
        self.win  = deque(maxlen=50)   # O(1) window, free eviction
        self.stat = Welford()          # O(1) mean + variance
    def on_tick(self, market, portfolio):
        px = market.mid('AAPL')
        self.win.append(px)            # O(1)
        self.stat.update(px)           # O(1)
        z = (px - self.stat.mean) / (self.stat.var**0.5 or 1)
        if z < -2: return Signal('AAPL','buy',5,px)
        return None

Slow code is not a style problem. It is a P&L problem.

Prices move while you compute. A signal that takes 50 ms to produce is a signal acting on stale data — the edge you detected has already been taken by someone whose loop was tighter. Complexity in a hot path is not an engineering nicety; it is the difference between providing liquidity and donating it.

There are two distinct questions and they pull in opposite directions. Latency is the time for one operation, end to end — and for a trader, latency is edge. Throughput is operations per second — and for an exchange, throughput is capacity under load. Batching raises throughput and adds latency. Tune for the role you actually play.

Then there is the part that averages hide. A mean of 1 ms with a p99 of 200 ms means one tick in a hundred is catastrophic — and it will be one of the volatile ticks, because that is when queues are deepest and the book is thickest. Report p50, p95 and p99. The p99 is what gets you picked off during a shock.

Five ways this week goes wrong

Every one of these has been submitted, defended in class, and quietly walked back. Read them before you write your benchmark, not after.

Three questions

Instant feedback, nothing recorded. Pick the best answer.

This week's work

Deliverable: an algorithmic improvement plan for one hot path, backed by a before/after microbenchmark. Graded 40 / 30 / 20 / 10 — improvement plan with correct complexity analysis, benchmark method and numbers, one O(n)→O(1) or O(n²)→O(n log n) improvement actually landed, and a clean branch with a readable write-up.

Reading before next class: shared/orderbook.py — the heap-plus-dict CLOB with lazy deletion, exhaustively covered by tests/test_orderbook.py because the book is the source of truth.