What Big-O leaves out

The first answer most people give is that both loops are O(n), so the difference must be a constant factor, and constant factors are an implementation detail. That answer is true and it ends the conversation, which is the problem. The interviewer has just told you the constant factor is two. They want to know where it comes from.

Big-O measures how the work grows as the input grows. It is the right tool for choosing between a quadratic and a linear algorithm, and it says nothing about how long one iteration takes. Two loops with the same complexity can differ by a factor of two, ten or a hundred, because one iteration of each makes the machine do different things.

A cost model is the habit of asking, for one iteration, what the hardware and the operating system actually do. You do not need cycle counts to do this. You need a short list of things that are expensive compared with an add or a compare, and the discipline to look for each of them in the code.

Here is the loop we will keep returning to in this module. A trading process receives quotes for many futures contracts and wants to act on the ones for a single contract:

struct Quote {
    std::uint32_t instrument;   // exchange's numeric id for the contract
    std::uint32_t seq;          // feed sequence number
    std::int64_t  price;        // in ticks, see Module 10
    std::int32_t  qty;
    std::uint8_t  side;         // 0 = bid, 1 = ask
};

void scan(const std::vector<Quote>& quotes, std::uint32_t wanted, Strategy& s) {
    for (const Quote& q : quotes) {
        if (q.instrument == wanted)
            s.on_quote(q);
    }
}

Walk one iteration in the order the machine executes it, and each step raises its own question.

1. The load of q. Where is this quote in memory, and is it already in a cache? A vector of quotes is one contiguous block, so the next quote is usually sitting in the cache line just fetched. A container of pointers to quotes would send every iteration somewhere new.
2. The comparison and the branch. Can the CPU predict which way the if will go? If one quote in fifty matches, the branch is easy to predict. If matches are random and frequent, a fair number of iterations pay for a misprediction.
3. The call. Is on_quote inlined, called directly, or called through a virtual function or a std::function? An inlined call costs nothing on its own; an indirect one is a load and a jump the compiler cannot optimise across.
4. What the call does. Does it allocate, copy a large object, take a lock, write a log line, or make a system call? Any one of these can cost more than everything else in the iteration together.

Over the course these become a checklist you can run on any hot path:

• Which code runs on every event, and which runs rarely?
• What data does one iteration touch, and how is it laid out?
• Does anything allocate, directly or inside a library call?
• Does anything copy more than it appears to?
• Are the branches and calls predictable, and can the compiler see through them?
• Can the code wait: on a lock, the kernel, the network, a disk, a log?
• Is the measurement that started this conversation measuring the loop at all?

The rest of the module takes these one at a time: memory layout and cache lines, allocation, copies and object layout, branches and indirect calls, virtual functions, type erasure, and benchmarking. Later modules take the waiting questions: threads in Module 4, the kernel in Module 6, the network in Module 7.

Back to the interview question. A strong answer names a method before it names a cause:

Both loops are O(n), so the difference is in what one iteration costs. I would compare the two loop bodies step by step: how the data is laid out and whether it is read in order, whether anything allocates or copies inside the loop, whether the calls are direct and inlinable, and whether either loop can block. Then I would check that the benchmark that showed the factor of two is measuring the loops themselves and not their setup.

Notice what is missing: no guessed numbers and no single buzzword. "It's probably cache misses" might be right, but said first it sounds like a guess. Interviewers at these firms hear that phrase all day; they are listening for the reasoning that would tell you whether it is true.