Why Big-O Ignores Constants
Big-O ignores constants because it describes how runtime scales with input size, and any fixed multiplier becomes irrelevant once the input grows.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 4 scenes and explore, respond, and learn as you go.
Why does big-O notation deliberately ignore constant factors even though they affect real running time?
Two sorting routines: one takes 5 seconds on 1,000 items and another takes 10 seconds on the same input. Are they equally efficient?
Intuition says 'no' — one is twice as fast right now. Yet textbooks say both are O(n log n) and treat them as equivalent. Something about the definition is hiding the constant the stopwatch measures.
A side-by-side growth rate chart for n log n (with a small constant) versus n log n (with a large constant) versus n², showing the constants wash out at scale and the growth class — not the constant — decides the curve.
Big-O tracks how cost scales when n gets large; a constant factor that never grows with n becomes irrelevant once the input does, so the notation deliberately drops it.
- formal epsilon-N definition proof
- comparison of big-O, big-Theta, and big-Omega
- empirical benchmarking of specific algorithms
- amortized or average-case analysis
- 01Two algorithms, one verdictslideSlot 1Hook
Two students each write an O(n log n) sort. Student A's implementation sorts 1,000 items in 5 seconds; Student B's takes 10 seconds on the same laptop. The class labels both as 'the same complexity.' Is that fair?
- Both algorithms have identical formal big-O class
- Measured running times differ by a factor of 2
- Textbook says they are equivalent — but the stopwatch disagrees
PhenomenonTwo implementations of the same algorithm class show a 2× measured gap on identical input.
QuestionIf big-O puts them in the same bucket, what exactly is big-O measuring that the stopwatch isn't?
- 02What does the stopwatch disagree with?interactiveSlot 2Tension
Predict which curve wins at small n and which wins at large n, then drag the input-size slider.
- Toggle between constant = 1 and constant = 10 on the same n log n formula
- Watch the gap shrink relative to an n² curve as n grows
- Notice that the constant disappears in the curve's shape, not in the runtime
PredictionDoubling the constant should roughly double the running time at every input size — so the slower curve stays slower forever.
Tempting intuitionBecause the constant affects real time at every n, big-O must be wrong, incomplete, or just a rough approximation.
- 03Big-O measures scaling, not speedslideSlot 3Reveal
Big-O asks: 'as n grows without bound, what's the dominant pattern of growth?' A constant multiplies runtime but never multiplies n, so the shape of the curve is set by the term attached to n — not the constant in front.
- Definition focuses on behavior as n → ∞, not at any fixed n
- Constant factor shifts the curve up or down but does not change its slope class
- An O(n²) algorithm will eventually overtake any O(n log n), even with terrible constants
EvidenceThe simulation shows the n² curve falling behind at small n but crossing and dominating beyond a crossover point — and that crossing is determined by the n² vs. n log n terms, not by the constant multipliers.
ConclusionBig-O ignores constants because constants describe today's hardware and code style, while the notation answers a different question: how does cost behave when the input grows?
Mechanism- 1Big-O only retains the term with the highest growth order because, at large n, that term dominates the sum regardless of its coefficient.
- 2A fixed constant factor stays fixed; it cannot 'outrun' a function of n once n is large enough, so it is discarded by the definition.
- 04Read it as a scaling questionslideSlot 4Takeaway
When a problem is reframed so that the input size doubles every iteration — server traffic growing year over year — apply the rule: ask which growth class wins, not which constant is smaller today.
- Identify the growth class first (n, n log n, n²)
- Treat the constant as unknown hardware-dependent tuning
- Re-derive the comparison under the 'n gets much larger' assumption
TransferA startup's user base grows 5× per year while its engineering team grows 2×. Each user request still costs c·n log n time. Should the team worry about the constant c or the growth class n log n?
Expected inferenceThe constant can be tuned away — better servers, caching, language rewrites — but n log n grows with the user base, so the team should treat the growth class as the real threat and the constant as a short-term lever.
Discussion threads for a Stage aren't available yet.
