P20 · Big-O classifier

🔊 Listen

1 · Big-O, formally

Definition (Sipser §7.1)

f(n) = O(g(n)) iff there exist constants c > 0 and n₀ ≥ 0 such that for all n ≥ n₀, f(n) ≤ c · g(n). Read it as "f is eventually upper-bounded by a constant multiple of g."

Two things to internalize. First, the constant c is allowed to be anything — so 1000n² and n² are both O(n²); the multiplicative factor doesn't change the class. Second, the bound only has to hold for large n. Tiny-n weirdness doesn't matter.

Related notation

Ω(g) = lower bound. f = Ω(g) iff ∃ c, n₀ : f(n) ≥ c · g(n) for n ≥ n₀.

Θ(g) = tight bound. f = Θ(g) iff f = O(g) and f = Ω(g) simultaneously.

o(g) = strict upper bound. f = o(g) iff f / g → 0.

🔊 Listen

2 · The classification recipe

🔊 Listen

3 · Animated demo · auto-plays · loops

🔊 Listen

4 · Pitfalls

O is one-sided. 3n² = O(n³) is true (n³ is also a valid upper bound), just not tight. If you want tight, use Θ.
The constant c matters for the proof, not the answer. When proving f = O(g), pick any constants that work. They don't have to be tight or small.
Log bases vanish. log₂ n and log₁₀ n differ by a constant, so both are O(log n) — no base specification needed in Big-O.
Multiplicative vs additive. O(n) + O(n²) = O(n²) — the larger wins. O(n) × O(n²) = O(n³) — multiplication adds exponents.

🔊 Listen

5 · Q&A defence notes

Q1. Why drop the constants?
Big-O is about asymptotic behaviour. 3n² and n² differ by a constant that doesn't change as n grows. For complexity theory, the shape of growth is what matters; multiplicative constants depend on machine details and aren't intrinsic to the algorithm.
Q2. Big-O vs Theta vs little-o?
O is an upper bound (could be loose). Θ is tight (matching upper and lower). o is strict — f = o(g) means f/g → 0, so f grows strictly slower than g. Example: 3n² = O(n³) is true; 3n² = Θ(n³) is false; 3n² = o(n³) is true.
Q3. What does "dominated by" mean rigorously?
For sufficiently large n (n ≥ n₀), the lower-order terms become arbitrarily small relative to the leading term. Removing them changes the value by at most a fixed multiplicative factor, which Big-O ignores anyway.
Q4. Why does Big-O use ≤ instead of strict <?
Because f = O(f) — every function is its own Big-O. With strict <, that would fail. The ≤ version is the right notion for "no worse than."

🔊 Listen

6 · Where to read more

Sipser: §7.1 (Big-O), §7.1 Examples 7.4–7.7. Lecture notes: Module 4 slide 2. Companion problem: P17 (growth-rate race, visual contrast).