Big-O Notation O-notation

Big-O Notation (O-notation)

Every other page in this topic uses Big-O; this is the page that takes its definition literally. Big-O is not a vibe about "fast" or "slow" — it is a precise mathematical statement about the existence of two witnesses, and once you can produce those witnesses you can prove a bound rather than assert it. That rigor is also what lets you spot the two misuses that quietly expose people who only pattern-match the notation.

The definition, read as a claim you must prove

Let T(n) be the operation count of an algorithm. We say T(n) = O(f(n)) if and only if:

there exist constants c > 0 and n0 ≥ 0 such that T(n) ≤ c·f(n) for all n ≥ n0.

Read it as an existence claim: to prove T(n) = O(f(n)) you must exhibit a specific c and n0 (the "witnesses") and show the inequality holds forever after. Two familiar rules are just consequences: constants drop (5n is O(n) — the witness c absorbs the 5) and lower-order terms drop (n2+3n+7 is O(n2)). The sibling notations Ω (lower bound) and Θ (tight bound) are compared side-by-side on Comparing Asymptotic Notations, and the equivalent limit-based test is on Overview of Asymptotic Analysis.

Proving a bound from first principles

Claim: T(n) = 3n2 + 5n + 100 is O(n2). Do not wave at it — find witnesses.

Pick c = 4. We need 3n2 + 5n + 100 ≤ 4n2, i.e. n2 ≥ 5n + 100, i.e. n2 − 5n − 100 ≥ 0. The positive root is n = (5 + √(25 + 400))/2 = (5 + √425)/2 ≈ 12.8, so the inequality holds for all n ≥ 13. Witnesses: c = 4, n0 = 13.

Verify the boundary (this is the step that makes it a proof, not a guess):

• n = 13: LHS = 3(169) + 65 + 100 = 672; RHS = 4(169) = 676. 672 ≤ 676 ✓.
• n = 12: LHS = 3(144) + 60 + 100 = 592; RHS = 4(144) = 576. 592 ≤ 576 is false — so n0 = 13 is exactly the threshold for this c.

Witnesses are not unique: choose c = 5 and the inequality n2 ≥ &frac52n + 50 holds from a smaller n0. Any valid (c, n0) pair proves the bound; the definition only demands that some pair exists. The method for producing the count T(n) from real code in the first place is on Understanding Time Complexity.

The two misuses the definition exposes

Misuse 1: "Big-O means worst case." False, and the definition proves it. Big-O bounds a function; best / worst / average describe which input scenario produced that function. They are independent axes. Linear search's best case is O(1), its worst case is O(n) — both are Big-O statements, about different functions. You can equally write the Ω of the worst case. Keeping the notation (O/Ω/Θ) separate from the case (best/worst/average) is the single clearest signal that you understand what you are saying.

Misuse 2: conflating O with Θ. Because O is only an upper bound, a linear algorithm is honestly O(n), but also O(n2), and even O(n100) — every one is a true (if useless) upper bound. When you want to say "the growth is exactly linear," the correct symbol is Θ(n). Casual speech says "O" and means "Θ"; write what you mean.

When O vs Ω vs Θ actually changes the answer

The distinction is not pedantry — it depends on the question you are answering:

• Describing an algorithm or choosing a structure → you want Θ, the true growth. "Mergesort is Θ(n log n)" is the useful statement; "mergesort is O(n2)" is true and worthless.
• Proving optimality → you need Ω, a bound on every possible algorithm. Comparison-based sorting has a lower bound of Ω(n log n): a comparison sort is a decision tree with n! leaves (one per possible ordering), so its height — the worst-case number of comparisons — is at least log2(n!) = Θ(n log n). For n = 20 that floor is log2(20!) ≈ log2(2.4×1018) ≈ 61 comparisons — no comparison sort can beat ~61 comparisons on 20 elements.

Now the two meet: mergesort's upper bound O(n log n) equals the problem's lower bound Ω(n log n), so mergesort is Θ(n log n) and provably optimal — not merely good, but impossible to beat asymptotically among comparison sorts. That conclusion is unreachable with O alone; it requires the Ω you would have skipped if you thought Big-O was the whole story.

Formal-notation pitfalls

• The "=" is an abuse of notation. T(n) = O(f(n)) really means T(n) ∈ O(f(n)) (membership in a set of functions). You never write O(f(n)) = T(n).
• Proving the wrong inequality. For O you bound from above (T ≤ c·f); flipping it proves Ω instead. Watch the direction.
• Giving a loose bound when asked for a tight one. "It's O(n2)" for a linear scan is technically true and will still lose you the point — interviewers want the tightest Θ.

Key takeaways

• Big-O is an existence claim: T(n) = O(f(n)) iff some c > 0, n0 make T(n) ≤ c·f(n) for all n ≥ n0. Prove it by exhibiting witnesses (e.g. c = 4, n0 = 13 for 3n2+5n+100 = O(n2)).
• Witnesses are not unique; any valid pair suffices.
• Keep the notation (O/Ω/Θ) separate from the case (best/worst/average) — "Big-O = worst case" is false — and say Θ when you mean tight.
• Ω earns its keep in optimality proofs: comparison sort is Ω(n log n) (decision-tree height log2(n!)), which is why mergesort's O(n log n) is provably the best possible.