An input bound of 100,000 bookings — what time complexity should you target, and why?
answer
- Read the constraint before designing
- How much work fits in a second
- Roughly ten to the eighth simple operations
- Plug the bound into each candidate class
- 10^5 squared is 10^10 — far over
basics
~20 sTarget O(n log n) or better. Quadratic work at n = 100,000 is about 10^10 operations, far past the rough budget of 10^8 simple operations per second, while n log n lands near 1.7 million — comfortably inside it.
solid answer
~50 sI read the constraint before I design anything. The working estimate is that a machine does on the order of `10^8` simple operations per second, so I take the stated bound, plug it into each candidate complexity, and compare. At n = 100,000, `n^2` is `10^10` — roughly a hundred seconds of pure looping, dead on arrival — while `n log n` is about 1.7 million and `n` is 100,000, both effectively free. So the bound is telling me to find something in the `n log n` class: sort once and scan, or maintain an ordered structure, rather than compare every pair of bookings. It is an estimate, not a guarantee — constants, memory traffic and a per-query multiplier can move it by an order of magnitude — but it reliably rules whole classes in and out, which is all a design decision needs.
go deeper
Memorise the ladder: roughly 10^8 simple operations per second, and n = 10^5 rules out quadratic. Be ready to plug a stated bound into two candidate complexities and say which one fits.
Explain where the estimate comes from and what it hides — constant factors, memory traffic, and the cost of an operation that is not actually simple. Show that you multiply a size bound by a query-count bound.
Demonstrate that you use the constraint to prune designs before writing code, and that you know when to stop trusting the estimate: near the 10^8 boundary you measure rather than argue about factors of two.
Own the framing that a stated bound is an assumption someone must keep true. Decide whether it is an enforced limit or an observation, and what the system should do the day real input exceeds it.
## The constraint is a design instruction An input bound printed in a problem statement or an API contract is not decoration. It is the strongest hint you get about which family of solutions is expected, and reading it first turns "think of an algorithm" into "think of an algorithm in this class" — a far smaller search. The instrument is a single back-of-the-envelope number: **a machine performs on the order of 10^8 simple operations per second**. "Simple operation" means an arithmetic step, a comparison, an array index — not a memory allocation, not a hash of a long string, not a disk read. Take the stated bound, evaluate each candidate complexity at that bound, and compare the result against 10^8 per second of budget. ## Working the example With a cap of 100,000 bookings per day: - `O(n^2)` — comparing every pair — is 10^10 operations. At 10^8 per second that is around 100 seconds. Not viable for a request, and not viable for a judge with a one- or two-second limit. - `O(n log n)` is 100,000 × ~17 ≈ 1.7 × 10^6. Two orders of magnitude *under* budget. - `O(n)` is 10^5. Invisible. The gap between the quadratic and the linearithmic option here is a factor of about 6,000. That is the point: the estimate does not need to be accurate to a factor of two, because the classes it separates differ by factors of thousands. ## The mapping worth memorising | Stated bound on n | Largest class that fits ~10^8 | Shape of the intended solution | | --- | --- | --- | | n ≤ 11–12 | O(n!) | try every ordering | | n ≤ 20–25 | O(2^n) | try every subset | | n ≤ 400–500 | O(n^3) | triple loop, dense table fill | | n ≤ 5,000 | O(n^2) | every pair, or a two-dimensional table | | n ≤ 10^5–10^6 | O(n log n) | sort, ordered structure, divide and conquer | | n ≥ 10^7 | O(n) or O(log n) | single pass, tallying, closed form | Read it in both directions. Going down, a bound tells you what you may afford. Going up, a suspiciously *small* bound is a signal that the expected solution is expensive per element — a cap of 18 is practically an invitation to enumerate. ## What the estimate does not model The 10^8 figure is a constant-factor placeholder, and constants are exactly what it hides: - **Per-operation cost varies by an order of magnitude across runtimes.** The same loop body is much cheaper in a compiled setting like C++ or Rust than in an interpreted one like Python or Ruby, and experienced competitors shade the estimate down toward 10^7 in the latter. Two teams can therefore reach opposite verdicts about the same algorithm — which is a fact about constants, not about asymptotics. - **Memory traffic dominates once the working set stops fitting in cache.** A linear pass over a contiguous block and a linear pass chasing pointers share a complexity class and can differ several-fold in wall time. - **Hidden factors inside a "simple" operation.** Comparing long strings, hashing large keys, or allocating per iteration each multiply the real cost. - **Multipliers stated elsewhere in the constraint block.** "n ≤ 10^5" together with "up to 10^4 queries" is a total budget of 10^9 unless each query is sub-linear. Always multiply the bounds together before judging. ## Two directional mistakes First, big-O is an **upper** bound. An `O(n^2)` label does not promise the algorithm ever performs n^2 work on real input — a doubly nested loop that breaks early, or one whose inner loop is bounded by a small constant in practice, can be fine. Estimate the operations actually executed, not the label. Second, asymptotic superiority promises nothing at small n. At n = 50 the `n^2` option is 2,500 operations and the `n log n` option is about 280; both are free, and the choice is decided by other costs entirely. ## How to say it in an interview Say the reasoning out loud before you design: "The cap is 10^5, so quadratic is 10^10 and out; I need the n log n class." That single sentence tells the interviewer you plan from constraints rather than pattern-matching, and it frames every design choice that follows.
- Does that mean an O(n^2) solution is automatically wrong at n = 100,000?For a genuine all-pairs scan, yes — 10^10 operations will not finish. But the label alone does not decide it, because big-O is an upper bound: a doubly nested loop whose inner loop is bounded by a small constant, or one that breaks early on a sorted prefix, may touch far fewer than n^2 pairs. Estimate the pairs actually visited, then judge.
- The constraint block also says up to 10,000 queries — how does that change your target?Multiply before you judge. Ten thousand queries against a 10^5 input means a per-query linear scan is 10^9 operations overall. That pushes the work off the query path: preprocess once in n log n, then answer each query in logarithmic or constant time. Whenever two bounds appear together, the budget is their product, not the larger one.
- Why is a rough estimate good enough to make a design decision on?Because the classes it separates differ by thousands, not by percentages. At n = 10^5, quadratic and linearithmic are about 6,000x apart, so even a tenfold error in the operations-per-second figure does not flip the verdict. The estimate is only unreliable near a boundary — around 10^8 operations — and there you benchmark instead of arguing.
It is the airline sizing box at the gate: you hold each candidate bag against it before packing anything, because the box tells you which shapes can possibly fit.
saying these in an interview costs you the question
- Quotes 10^8 as an exact machine speed rather than an estimate
- Designs before reading the input bound at all
- Ignores a query-count multiplier stated beside the size bound
- Assumes the complexity class alone settles wall-clock time
- Thinks n log n and n^2 are close at n = 100,000