Why is it a misconception that Big-O notation means worst-case running time?

## Two independent axes Most complexity statements involve two separate choices that the folklore phrase "Big-O is worst case" collapses into one: 1. **Which function are we talking about?** An algorithm doesn't have one running time — it has a running time *per input*. To get a function of the input *size* n, you must aggregate over all inputs of that size: take the maximum (**worst case**), the minimum (**best case**), or the expectation under some distribution (**average case**). Each choice yields an ordinary function of n. 2. **What kind of bound are we stating about it?** Upper (**O**), lower (**Ω**), or tight (**Θ**). Any combination is legitimate, giving a 3-by-3 grid of meaningful statements. "Worst case is O(n^2)": no input costs more than quadratic. "Worst case is Ω(n^2)": some family of inputs forces quadratic. Both together: "worst case is Θ(n^2)" — the standard complete characterization of an algorithm's worst behavior. "Best case is Ω(n)": even the most favorable input costs at least linear time. ## Making 'best case Ω(n)' concrete Consider a validation pass that must inspect every one of n product records to confirm each has a well-formed key — it never exits early, because a clean record tells it nothing about the others it hasn't read. Its most favorable input still costs a full scan, so the honest statement is: *best case Ω(n)* (indeed Θ(n)). A candidate who believes "Ω means best case" tends to parse "best case Ω(n)" as redundant or contradictory; a candidate who has separated the axes reads it instantly as "even at its luckiest, it's at least linear". Contrast an early-exit search that returns on the first record matching a target key: its best case (match in position one) is Θ(1), while its worst case (no match) is Θ(n). Same algorithm, different case functions, each with its own tight bound — the grid in action. ## Where the conflation comes from The folklore isn't random; it fossilizes two real conventions: - **Unqualified O-statements default to worst case.** When someone says "this algorithm is O(n log n)" with no case named, they conventionally mean the worst case is O(n log n). That's the natural default because a worst-case upper bound covers *every* input — it is the strongest guarantee expressible with one simple claim, and guarantees are what callers want. - **Ω appears most often in lower-bound results**, which are frequently proved via hard instances, and hard instances feel "worst-case-ish". But the notation itself is case-agnostic. So the shorthand is defensible; promoting it to a definition is the error. The tell in an interview is whether the candidate can *generate* a statement like "best case Ω(n)" and explain what it asserts, rather than pattern-matching O to worst and Ω to best. ## Why the distinction earns its keep Precision here changes what you can conclude. "Worst case O(n^2)" alone leaves open that the algorithm is actually linear on every input (the bound may be loose). Adding "worst case Ω(n^2)" — a witness family of inputs forcing quadratic work — closes the gap and pins the worst case at Θ(n^2). Conversely, best-case lower bounds are how you argue an algorithm *cannot* be made to exit early: if every run must read all the input it touches, no amount of cleverness inside that algorithm gets below linear. Keeping "which case" and "which bound" as separate slots is what lets these arguments be stated — and checked — cleanly.