The Cost Model: What Big-O Hides

Suppose you show me an O(n) loop and say the algorithm is optimal. My next question is: what does one iteration make the machine do?

Consider two implementations that process n $AAPL market updates. Both use one O(n) pass. If a benchmark measures one at 5 microseconds per update and the other at 10, their growth rates agree while their running times do not. We need to inspect the work inside the loop to explain the difference.

What Big-O hides

Big-O describes how total work grows with n. It treats each iteration as a unit, even though two iterations can contain very different machine operations. A loop may follow scattered pointers, request heap memory, copy a large object, make an indirect call, or wait for the operating system. Each operation adds work that O(n) leaves unspecified.

A cost model accounts for that work. When we read a hot path, we trace the operations that repeat and ask which ones can dominate an iteration.

A hot path is code that runs repeatedly while the system handles its main workload. In a trading system, it often processes market updates, changes order state, or decides whether to send an order. An extra operation in this path repeats for every relevant update, so small per-iteration costs accumulate across the stream.

The nine hot-path questions

When you inspect a hot loop, these questions give you a useful order of attack:

1. What code runs again and again?
2. What data does each iteration read?
3. Where does that data live in memory?
4. What function calls happen inside the loop?
5. Can those calls allocate memory?
6. Can those calls copy more bytes than they appear to copy?
7. Can the CPU or compiler predict the path through this code?
8. Can this code wait on the OS, a lock, the network, or a log?
9. Are we measuring the real hot path?

The rest of Module 1 answers these questions through the same update loop. Locality covers questions 2 and 3, allocation covers question 5, copies cover question 6, and dispatch and branching cover questions 4 and 7. The measurement article returns to question 9. Later modules handle operating-system and network waits from question 8.

C++ shape

We will keep coming back to this loop:

Copy
struct MarketUpdate {
    std::uint64_t sequence;
    char symbol[8];      // "AAPL"
    std::int64_t price;  // 19010
    std::int32_t qty;    // 100
};

void handle(const std::vector<MarketUpdate>& updates) {
    for (const MarketUpdate& update : updates) {
        if (update.symbol[0] == 'A') {
            apply_update(update);
        }
    }
}

Follow one iteration in execution order. The loop obtains a reference to the next MarketUpdate, reads symbol[0], evaluates the branch, and may call apply_update(update). Each step raises a more specific question. Is the update already in cache? Can the processor predict the branch? What does apply_update read, copy, or allocate?

Loop bookkeeping still takes instructions, though it is rarely the first concern in code shaped like this. The data access, branch, and function call can lead to much more work, so we inspect them first and confirm the result with measurements.

Visual model

Big-O describes how the loop scales. The cost model follows the operations inside one iteration.

In interviews

An interviewer may give you the asymptotic result and then ask about the machine-level cost. A useful answer stays close to the code:

• "Why might your O(n) loop be slower than another team's O(n) loop?" → "I would compare one iteration from each loop: the memory it reads, the objects it copies or allocates, the functions it calls, and the branches the processor encounters."
• "Walk me through this hot path." → Follow one input through the loop, then expand each read, branch, and call into the work it causes.
• "How would you make this faster?" → Point to a suspected cost in the code, explain the mechanism, and describe the measurement you would use to check it.

The next article follows the first memory read and asks where the MarketUpdate lives.