A downsampling pass costs 5n log n + 200n steps — is O(n log n) an honest label?
answer
- the label is about the limit, not today
- solve for where the two terms are equal
- 5 log2 n versus 200
- log2 n above 40 means n above 2^40
- the dropped term leads below a trillion
basics
~20 sFormally yes: for large enough n the 5n log n term dominates. But 200n is the larger term for every n below roughly 10^12, so the label predicts the growth shape, not the runtime anyone will measure.
solid answer
~50 sThe label is correct and nearly useless on its own, and I would say both halves out loud. Correct, because asymptotic classification asks which term wins as `n` grows without bound: `5n log n` overtakes `200n` once `5 log2 n > 200`, that is `log2 n > 40`, that is `n > 2^40`, about `1.1x10^12`. So the sum is `Theta(n log n)` and the `200n` is a genuine lower-order term. Nearly useless, because every batch this service will ever see is below that crossover — at a million samples the terms are `10^8` and `2x10^8`, so the *dropped* term is the bigger one. The class tells me how cost bends when volume grows; it does not tell me where the time goes today. For that I measure, and I attack the 200 constant before I attack the log factor.
go deeper
Know that a constant multiplier, however large, does not change which growth class an expression belongs to. Being able to say why 200n is the lower-order term of that sum is the whole ask at this level.
Show the crossover calculation: set the two terms equal, solve for n, and report the size where the ranking flips. That single step converts a definition into a usable engineering number.
Demonstrate that you keep the class and the measurement in separate boxes and use each for its own job. An interviewer wants to see you resist optimising the term the notation highlighted rather than the term the profile did.
Own the vocabulary a team uses to argue about performance. You decide when a discussion is a scaling question, settled by growth class, and when it is a constant-factor question, settled only by measurement on real data.
## What the label promises, precisely Saying a cost of `5n log n + 200n` is `O(n log n)` is a claim about **eventual growth**: there exist constants `c` and `n0` such that for every `n` beyond `n0` the total is at most `c * n log n`. It says nothing whatsoever about the runtime at any particular `n`, and nothing about which term contributes most at the sizes you run. Those are three separate questions, and conflating them is the mistake this question is built to catch — in both directions. The first direction is the classic error: "you cannot drop `200n`, 200 is a big number". The size of a constant is irrelevant to classification. `200n` grows linearly; `5n log n` grows faster than linearly; therefore their ratio `5 log n / 200` grows without bound and the linear term is asymptotically negligible. The label is not a lie. The second direction is the one that costs money: "it is `O(n log n)`, so the log factor is where the time goes". Solve for the crossover. `5n log2 n > 200n` reduces to `log2 n > 40`, so `n > 2^40 ≈ 1.1x10^12`. Below a *trillion* samples, the term the notation invited you to discard is the dominant one. ## Where the terms actually stand at real sizes | n | 5n log2 n | 200n | which term leads | |---|---|---|---| | 10^3 | 5x10^4 | 2x10^5 | the linear term, 4x | | 10^6 | 1.0x10^8 | 2.0x10^8 | the linear term, 2x | | 10^9 | 1.5x10^11 | 2.0x10^11 | the linear term, still | | 10^12 | 2.0x10^14 | 2.0x10^14 | roughly equal | The practical reading: on this routine, a 20% cut to the per-sample constant work is worth more than eliminating the log factor entirely, at every input size the service will encounter. That is a profiling and constant-factor conversation, not an algorithms conversation — and knowing which of the two you are in is the senior skill here. ## Why the label is still worth keeping None of this makes asymptotics decorative. The class is the only part of the cost that answers "what happens at 10x, 100x, 1000x volume". Constants are measured, machine-specific, and change when the code, the data layout or the hardware changes; the growth class does not. So the two artifacts do different jobs: - **Growth class** — predicts the *shape*: is a volume increase absorbable at all, and does the cost per element rise? - **Measured constants** — predict *today's* wall clock and tell you where to optimise first. A good answer keeps both and never substitutes one for the other. The failure mode of ignoring the class is discovering at 100x volume that the curve bends; the failure mode of ignoring the constants is spending a sprint removing a log factor that was never in the critical path. ## The general habit: find the crossover Whenever you are handed two cost expressions, the useful move is not to rank their classes but to solve for where they cross, and then ask which side of the crossover you live on. Two examples worth having ready: - `5n log n` versus `200n`: crossover near `10^12`, so in practice the linear term rules. - `n^1.5` versus `n log^2 n`: divide both by `n` and compare `sqrt(n)` against `(log2 n)^2`. Any positive power of `n` eventually beats any fixed power of a logarithm, so `n^1.5` is asymptotically larger — but at `n = 10^4` the values are 100 and about 177, and the crossover sits near `n ≈ 7x10^4`. Asymptotically worse, cheaper below the crossover. That second one also shows how to settle mixed-term comparisons at a whiteboard without a calculator: cancel common factors, then compare a power of `n` to a power of `log n`, and remember that the power of `n` always wins in the limit no matter how small its exponent or how large the log's. The log base never changes the ranking either — changing base multiplies by a constant — though it does move the crossover, which is why the base matters the moment you put real numbers in. ## What to say when challenged A short, complete answer sounds like: "The label is right — `200n` is lower-order and drops out above roughly a trillion samples. It is also not where our time goes: below that crossover the linear term leads, so I would profile the per-sample work first. I keep the `O(n log n)` label because it is what tells us a 10x volume increase costs about 11x, not 100x." That answer shows the notation is understood as a tool with a defined scope rather than as a performance verdict.
- Which grows faster, n^1.5 or n log^2 n, and how do you settle it without a calculator?Cancel the shared `n` and compare `sqrt(n)` with `(log2 n)^2`. Any positive power of `n` eventually outgrows any fixed power of a logarithm, so `n^1.5` is asymptotically larger. The crossover is late though — at `n = 10^4` the values are 100 versus about 177, and they meet near `n = 7x10^4` — so below that the `n^1.5` expression is actually the cheaper one. The log base changes only the crossover, never the ranking.
- So when is the O(n log n) label the number you should act on?When the question is about scaling rather than about current wall clock: sizing headroom, deciding whether a projected 10x in volume is absorbable, or comparing two designs whose constants you cannot yet measure. `n log n` costs about 11x more at 10x the data while a quadratic step costs 100x — that comparison survives any constant. For "why is this slow right now", measure instead.
- Your teammate says the 200 constant proves the implementation is bad. Fair?Not by itself. A constant of 200 element operations per sample might be irreducible work — validation, unit conversion, writing an output record — or it might be avoidable overhead. The constant is a measurement pointing at where to look, not a verdict. The useful next step is a profile that attributes those 200 operations, not an argument about notation.
saying these in an interview costs you the question
- You cannot drop 200n because 200 is a large constant
- The n log n term is obviously where the time goes
- Asymptotic labels predict measured runtime
- Constants never matter once you know the class
- Changing the logarithm base changes the growth class