Is calling a single non-nested catalog loop 'O(n^2)' wrong, technically true, or both — and what should a precise reviewer say instead?
answer
- which direction does O bound?
- a true claim can still mislead
- loose upper bounds are always true
- accusing slowness needs a lower bound
- the tight two-sided notation is Theta
basics
~20 sTechnically true, practically misleading. Big-O is only an upper bound, so a linear scan is O(n^2) in the same trivial sense it is O(n^3). The implied complaint — quadratic growth — is false: the tight bound is Theta(n).
solid answer
~50 sThe comment is formally true and substantively wrong. `f(n) = O(g(n))` only claims f grows *no faster* than g, so a loop doing constant work per record — Θ(n) time — satisfies O(n^2), O(n^3), and even O(2^n); loose upper bounds are always true. But a review comment saying "this is O(n^2)" is meant as an accusation of quadratic growth, and that accusation is a *lower-bound* claim: to say something is slow you must argue Ω(n^2), typically by exhibiting the mechanism (say, a nested rescan per record) that forces it. Here no such mechanism exists, so the complaint fails. The precise review language is Theta: "this loop is Θ(n)" makes the two-sided, tight claim. Everyday speech uses O to mean Θ; in a review, where the difference is the whole dispute, use the notation that says what you mean.
code
pseudocode · 5 linescount = 0
for i in 0..length(catalog)-1
if catalog[i].price < threshold
count = count + 1
return countgo deeper
Be ready to say what an upper bound is and to recognize that a single loop with constant work per element is linear time. Knowing that O(n) functions technically satisfy O(n^2) is a strong extra.
An interviewer expects you to resolve the paradox cleanly: the statement is formally true because O only bounds above, yet the implied accusation is false, and Theta is the notation for the tight claim. Know the O/Omega/Theta directions cold.
Demonstrate the review craft: an accusation of slowness must exhibit the mechanism that forces the work, making it falsifiable and actionable. Show you can turn a notation dispute into a concrete line-level question about the code.
Own the communication standard: teams waste cycles on true-but-useless complexity claims. Set the norm that performance objections name mechanisms and tight bounds, and that asymptotic disputes end with a measurement or a proof, not louder notation.
## The scene A reviewer looks at a loop that walks a product catalog once, doing constant work per record, and comments: "this scan is O(n^2)". Untangling whether that is wrong requires being exact about what each notation claims. ## What Big-O actually asserts `f(n) = O(g(n))` means: there exist a constant `c > 0` and threshold `n0` such that `f(n) <= c * g(n)` for all `n >= n0`. It is purely an **upper bound** — the growth-rate analogue of `<=`. And just as `5 <= 100` is true, a function that grows linearly sits comfortably below `c * n^2` for large n. So the literal statement "this loop's running time is O(n^2)" is **true**. So is O(n^3). So is O(2^n). Upper bounds are cheap: making one looser never makes it false. ## What the reviewer meant Nobody writes "O(n^2)" on a review to certify a generous upper bound. The intended claim is "this code *grows quadratically* — it will blow up on a big catalog." That is a fundamentally different kind of statement, because *slowness is a lower-bound claim*. To establish that a computation is at least quadratic you must show `f(n) >= c * n^2` eventually — Big-Omega, written Ω(n^2). And that requires exhibiting the mechanism that forces the work: a nested loop that rescans the catalog per record, a per-record operation that itself walks the data, a hidden linear-cost call inside the loop body. A single non-nested loop with constant-cost body has no such mechanism; its time is at most `c * n` and at least `c' * n`, which together give the tight, two-sided bound **Θ(n)**. ## The three notations, aligned | Notation | Direction | Everyday analogue | Use it to claim… | |---|---|---|---| | `O(g)` | upper | `<=` | "no worse than" — a guarantee | | `Ω(g)` | lower | `>=` | "at least this costly" — an accusation of slowness | | `Θ(g)` | both | `=` | "exactly this growth" — the tight, informative claim | The asymmetry is worth internalizing as a direction-of-claim rule: **to promise speed, prove O; to accuse slowness, prove Ω; to characterize, prove Θ.** A review comment quoting only an upper bound literally cannot establish that anything is slow — the bound might be (and here, is) wildly loose. ## Why the loose usage exists at all Colloquially, engineers say "this is O(n log n)" when they mean Θ(n log n). The convention survives for two reasons. First, upper bounds are usually what analyses actually prove and what callers care about as guarantees. Second, in casual speech listeners reliably interpret the stated class as tight. This is a well-understood abuse of notation, and it is harmless right up until the tightness *is* the dispute — as in this review. Then the shorthand collapses: "O(n^2)" as an accusation and "O(n^2)" as a loose-but-true bound are different statements wearing the same clothes. ## What the review should say If the reviewer believes the loop is fine: nothing, or "Θ(n), looks right." If the reviewer believes it is genuinely quadratic, the comment must point at the mechanism: "the lookup inside this loop walks the whole catalog, so the total is Ω(n^2)" — a checkable, falsifiable claim. Precision here is not pedantry; it is what makes the comment *actionable*. "This is O(n^2)" invites a true-but-useless rebuttal ("so is every linear scan"), while "this inner call makes it Θ(n^2)" names exactly the line to fix. ## The transferable lesson Asymptotic notation is a set of claims with directions. Checking the direction — does this statement bound from above, below, or both? — resolves most notation disputes instantly, and it is the habit interviewers are probing when they pose exactly this scenario.
- How should the review comment have been phrased if the reviewer genuinely suspected quadratic behavior?By naming the mechanism, not the class: "this call inside the loop rescans the catalog, making the total Ω(n^2)" — a checkable claim pointing at the offending line. Slowness accusations are lower-bound claims, so they need a witness that forces the work. Absent a mechanism, the correct comment is the tight bound: "this loop is Θ(n)."
- Why do engineers say 'this is O(n log n)' in everyday speech when they mean the tight bound?It's a conventional abuse of notation: upper bounds are what analyses typically prove and what callers want as guarantees, and listeners reliably read the stated class as tight. That's fine in conversation. The distinction only bites when tightness is the actual dispute — in specs, reviews, and proofs — and there Theta or an explicit lower bound should be used.
Labeling a 100-gram letter 'under 10 kilograms' is true but misleading — a loose upper bound invites a conclusion it cannot support.
saying these in an interview costs you the question
- Insists a linear loop cannot be O(n^2) because Big-O states actual growth
- Uses O(n^2) to mean 'grows quadratically' and cannot name Theta when pressed
- Cannot explain that claiming slowness requires a lower bound
- Treats the distinction as pedantry with no actionable consequence