skip to content

You shaved a log factor off a report's ordering phase but wall time barely moved - why?

level: middleimportance: should knowfreq 55%

answer

  1. the cost of a routine is a sum
  2. which term grows fastest
  3. big-O drops lower-order terms
  4. how much could this change buy at most
  5. quadratic next to linear wins

basics

~20 s

Total cost is a sum of terms, and the ordering phase was not the dominant one. A quadratic pairing pass still sets the runtime, so removing a log factor from a smaller term changes nothing measurable.

solid answer

~50 s

A routine's cost is the sum of its phases, and the optimize phase has to attack the term that dominates that sum. Here the pairing pass is `O(n^2)` and the ordering pass was `O(m log m)`; turning the ordering into `O(m)` leaves `O(n^2 + m)`, which is still quadratic, so the measurable runtime barely budges. Before optimizing anything I state the per-phase cost with its own size variable - the number of pairs `m` is not the number of records `n` - and then ask which term grows fastest at the sizes I actually expect. Two caveats keep this honest: asymptotics only tell you which term wins *eventually*, so at real input sizes a large constant on the 'small' term can still dominate; and if `m` is enormously larger than `n`, the ordering term may genuinely be the bottleneck. So I name the terms, sanity-check them against expected sizes, then optimize the biggest one.

code

pseudocode · 14 lines
pseudocode
// phase 1 - compare every refund record against every other
for i in 0..n-1
    if used[i]
        continue
    for j in 0..n-1
        if j != i and not used[j] and amounts_match(rec[i], rec[j])
            link(i, j)
            used[i] = true
            used[j] = true
            break

// phase 2 - put the m linked pairs into report order
// was: order(links)          -> O(m log m)
report = bucket_order(links)  // now: O(m)

go deeper

for a junior

Be ready to add up the phases of a routine and say which term is largest. Recall that big-O drops lower-order terms, so improving a smaller term often leaves the overall class unchanged.

for a middle

Explain the mechanics: give each phase its own cost and its own size variable, write the sum before and after your change, and say why a linear ordering phase disappears next to a quadratic pairing pass.

for a senior

Demonstrate the judgement of bounding a proposed speedup by the phase's share of the total before spending effort, and of checking asymptotic reasoning against the input sizes the system really sees.

for a principal

Own where optimization effort goes across a codebase: which measurements justify a rewrite, when a quadratic path is acceptable because its inputs are bounded, and how to stop teams from shipping invisible micro-improvements.

## Cost is a sum, and only one term usually matters A multi-phase routine costs the sum of its phases. If phase one is `O(n^2)` and phase two is `O(m log m)`, the whole thing is `O(n^2 + m log m)`. Big-O deliberately discards constant factors and lower-order terms, so when `m` is on the order of `n`, that expression collapses to `O(n^2)` - and any improvement confined to the second term collapses with it. This is why "I made the sort linear" can be a completely true statement about a change that nobody can measure. The change is real; it is just invisible behind a term that grows faster. ## Finding the dominant term before you touch anything The discipline is mechanical: 1. **Split the routine into phases** and give each one its own cost - and its own size variable. The number of matched pairs `m` is not the number of records `n`; conflating them is how people mislabel the bottleneck in the first place. 2. **Write the sum**, then ask which term grows fastest as the inputs grow. 3. **Check that against the sizes you actually expect.** Asymptotic dominance is a statement about large enough inputs. It does not promise the dominant term is the biggest contributor at n = 200. 4. **Only then choose what to optimize** - and say what the new sum would be *before* you write the change. If the new sum has the same leading term, you have your answer already and you can spend the effort elsewhere. ## The direction of the claim matters Several true-sounding statements about this are wrong in a way interviewers listen for: - `O(n^2)` is an **upper** bound. Labelling a phase quadratic does not promise it ever behaves quadratically on your data; the pairing loop may exit early on nearly all real inputs. - An asymptotically better algorithm promises nothing at small `n`. Constants win there. That is the same reason mainstream sorts hand small runs to insertion sort instead of recursing further - the asymptotically worse algorithm is genuinely faster in that range. - "The other term is lower-order" is a claim about growth, not about the current profile. A cheap-looking term with a heavy constant can dominate today and stop dominating as data grows, which is why the honest answer names both the asymptotics and the expected sizes. ## Ceiling on any speedup Even a perfect optimization of one phase is bounded by that phase's share of the total. If ordering is a tenth of the work, deleting it entirely buys you about eleven percent - and shaving a log factor off it buys far less. The reviewer's question is therefore not "is this change an improvement?" but "what is the largest speedup this change could possibly produce?" If the answer is a few percent while an `O(n^2)` loop sits next to it, the change is spending review time and risk on the wrong term. ## What to do instead Attack the leading term. In a pairing pass, the standard moves are the ones this phase of the method is made of: index the records by the matching key so each record consults a bucket of candidates instead of every other record, which trades memory for the inner loop; sort by the key so matches are adjacent and one sweep replaces the nested scan; or prune - stop the inner scan once the ordering guarantees no further candidate can match. Each of these turns `O(n^2)` into something with `n log n` or expected-linear behaviour, and each moves the *leading* term, which is what makes the wall clock move. ## Saying this in the interview When an interviewer asks you to optimize, the strongest opening is not a technique - it is a decomposition: "the cost is roughly this term plus that term; this one dominates; that is what I will attack, and here is the sum I expect afterwards." It shows you optimize by analysis rather than by instinct, and it protects you from the most common self-inflicted wound in this phase, which is spending your remaining minutes making a small term smaller. ## The reviewer's chair Reviewing someone else's optimization, ask three questions: which term does this touch; what is the whole sum before and after; and what measurement is claimed. If the leading term is unchanged, the correct review comment is not "this is wrong" - the change may be perfectly good - but "this cannot move the number you say it moves, and here is the term that can."

  • Under what sizes would optimizing that ordering phase actually have been the right call?
    When the number of linked pairs dwarfs the number of records - say the matching is loose and each record links to many others, so m grows far faster than n. Then `m log m` can exceed the pairing pass in practice, and the ordering phase is genuinely the leading cost. That is why each phase needs its own size variable: assuming m is about n is what hides the real bottleneck.
  • How would you attack the pairing pass itself?
    Stop comparing every record with every other. Index the records by the matching key so each one consults only the candidates that could match, which trades memory for the inner loop, or sort by that key so candidates are adjacent and one sweep replaces the nested scan. If the ordering also bounds the key, you can prune - break out of the inner scan once no remaining candidate can match. All three move the leading term.
  • Reviewing this change, what comment do you leave?
    Not that it is wrong - a linear ordering pass is fine - but that the claimed speedup is impossible: the routine is still quadratic in records, so the largest win this change can produce is bounded by the ordering phase's share of the total. I would ask for the before-and-after sum written out, and point at the nested pairing loop as the term worth the same effort.

saying these in an interview costs you the question

  • Optimizes the phase that is easiest to change
  • Treats every asymptotic improvement as a measurable win
  • Uses one size variable for phases with different sizes
  • Thinks big-O promises behaviour at small inputs
  • Cannot state the total cost as a sum of phases

context

resolving links…