Asymptotic Notation: Big-O, Omega, Theta

Let f(n) and g(n) be functions from the positive integers (or positive reals) to the non-negative reals — these represent running time, memory use, or any other cost as a function of input size n, following directly from the idea of Measuring Running Time as a Function of Input Size. Asymptotic notation compares f against a simpler reference function g, usually a clean expression like n, n², n log n, or 2ⁿ, and classifies how f grows relative to g once n is large enough. The key philosophical move is to allow two kinds of slack. First, constant-factor slack: we don't care whether f(n) is bounded by g(n) or by 5·g(n) or by 0.001·g(n) — any positive constant multiple counts, since constants depend on hardware and implementation details we want to abstract away. Second, finite-exception slack: we don't care what happens for small n, since real systems are judged by behavior at scale, and any finite set of small inputs can be handled by special-casing or simply waiting for the trend to kick in. Both slacks are made precise by the pair (c, n₀): c is the constant multiple, n₀ is the threshold beyond which the bound must hold, and n₀ is exactly the boundary that separates "small, exception-prone inputs" from "large, asymptotic-regime inputs."

Big-O (upper bound). We say f(n) = O(g(n)) if there exist positive constants c and n₀ such that ``` 0 ≤ f(n) ≤ c · g(n) for all n ≥ n₀ ``` This says f eventually never exceeds some constant multiple of g. Big-O gives a ceiling: the algorithm is at least as good as this bound, though possibly much better.

Big-Omega (lower bound). We say f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that ``` 0 ≤ c · g(n) ≤ f(n) for all n ≥ n₀ ``` This says f eventually is always at least some constant multiple of g. Big-Omega gives a floor: the algorithm can never do better than this bound, no matter how cleverly it is analyzed.

Big-Theta (tight bound). We say f(n) = Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that ``` 0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀ ``` Equivalently, f(n) = Θ(g(n)) exactly when f(n) = O(g(n)) and f(n) = Ω(g(n)) with the same g. Θ says f and g grow at exactly the same rate, up to constants — g is a perfectly tight description of f's asymptotic behavior. Formally, each of O(g), Ω(g), Θ(g) denotes a set of functions (all functions satisfying the inequality), and "f(n) = O(g(n))" is standard abuse of notation for "f(n) ∈ O(g(n))."

Working with asymptotic notation is a skill of constructing witnesses and verifying inequalities — it is not about staring at a graph and guessing. The general recipe: 1. State the claim. Decide what you're proving: f = O(g), f = Ω(g), or f = Θ(g). 2. Set up the target inequality. For O, you need f(n) ≤ c·g(n); for Ω, c·g(n) ≤ f(n); for Θ, do both (often as two separate O and Ω proofs). 3. Bound f(n) algebraically. Use crude but valid inequalities — e.g., drop lower-order terms in the right direction, replace a sum by an integral bound, or bound each term by the largest term times the number of terms. 4. Solve for a threshold n₀. After bounding, you'll get an inequality in n that is easy for large n; find the n₀ beyond which it is guaranteed true. 5. State the witness (c, n₀) explicitly and double-check by substitution, especially at n = n₀ and at a couple of larger sample values. ``` FUNCTION verify_big_O(f, g, c, n0): // Attempts to certify f(n) = O(g(n)) using witnesses c, n0. // In practice f and g are algebraic expressions; here we // describe the check performed for a claimed witness pair. for n = n0 to n0 + K: // K = a handful of spot checks if f(n) > c g(n): return "WITNESS FAILS at n = " + n // Spot checks alone never PROVE the bound for all n >= n0; // an algebraic argument (below) is required for a real proof. return "witness passes spot checks; verify algebraically" FUNCTION prove_polynomial_big_O(a_k, a_{k-1}, ..., a_0, k): // Prove that f(n) = a_k n^k + ... + a_1 n + a_0 is O(n^k) // when a_k > 0, using the standard "sum of absolute values" trick. A = |a_k| + |a_{k-1}| + ... + |a_0| // one constant, sum of coefficients n0 = 1 c = A // Claim: for all n >= n0 = 1, // f(n) <= |a_k| n^k + |a_{k-1}| n^{k-1} + ... + |a_0| // <= |a_k| n^k + |a_{k-1}| n^k + ... + |a_0| n^k (since n^i <= n^k for i <= k, n>=1) // = A n^k return (c, n0) // witness pair proving f(n) = O(n^k) ``` The second routine is not pseudo-magic — it is the actual algebraic technique used to prove that every degree-k polynomial with positive leading coefficient is O(n^k): bound every lower power of n by n^k itself (valid once n ≥ 1), collapse the polynomial into a single constant times n^k, and read off the witness. For Ω, the analogous trick isolates the leading term and shows the other terms cannot cancel it out for large n. For example, to show f(n) = n² − 100n = Ω(n²), write ``` f(n) = n² − 100n = n²(1 − 100/n) ``` Once n ≥ 200, the factor (1 − 100/n) ≥ 1/2, so f(n) ≥ (1/2)n² for all n ≥ 200. This gives witness c = 1/2, n₀ = 200, proving f(n) = Ω(n²). Combined with the earlier polynomial trick showing f(n) = O(n²) (with c = 101, n₀ = 1, say), we conclude f(n) = Θ(n²) — the −100n term is asymptotically irrelevant, swallowed by the constant-factor slack.

Strictly speaking, O, Ω, and Θ are not algorithms themselves — they are a notation for stating and proving claims about algorithms' resource usage. But "using" the notation correctly has its own complexity in the sense of proof effort, and there is a genuine correctness question: what does it mean for a claimed bound to be true, and how do you verify a witness rigorously rather than just plausibly?

Correctness is definitional, and proofs are existence proofs. To prove f(n) = O(g(n)), you must exhibit specific numbers c and n₀ and then verify, by an algebraic chain of inequalities valid for all n ≥ n₀ (not just a few sample values), that f(n) ≤ c·g(n). This is a ∃c, n₀ ∀n ≥ n₀ statement — the constants are chosen once and must work for every sufficiently large n simultaneously. A single counterexample at some enormous n does not disprove the claim, because a different, larger n₀ might repair it, but if no finite n₀ can ever repair it — if f(n)/g(n) → ∞ — then the O-claim is false and no witness exists at all.

Why the "sum of absolute values" trick is valid, using the polynomial example again: for n ≥ 1, every term aᵢnⁱ (i ≤ k) satisfies |aᵢ|nⁱ ≤ |aᵢ|nᵏ, since nⁱ ≤ nᵏ once n ≥ 1 and i ≤ k. Summing k+1 such inequalities and using the triangle inequality |f(n)| ≤ Σ|aᵢ|nⁱ gives |f(n)| ≤ (Σ|aᵢ|)nᵏ = A·nᵏ. This is not a heuristic — it is a fully rigorous derivation, and it generalizes: any bound proof reduces to finding a chain of true inequalities connecting f(n) to c·g(n).

Θ is the only notation that claims tightness, and this has a real consequence: Θ(g) is what you want when comparing algorithms, because O alone can be a loose, uninformative upper bound. Bubble sort is O(n³) (true but wasteful to state) and also O(n²) (tight) — both are valid O-claims, since any true upper bound multiplied by anything larger remains an upper bound (O is closed upward: if f = O(g) and g = O(h), then f = O(h), by chaining the witness constants c₁c₂ and n₀ = max(n₀₁, n₀₂)). This means "f = O(n²)" carries less information than "f = Θ(n²)"; the latter additionally certifies that no smaller g would do, since Ω(n²) is also established.

Space and other resources are covered by the same notation. Nothing in the definitions is specific to time — f(n) can equally be memory words used, comparisons made, cache misses incurred, or messages sent in a distributed protocol. The formal apparatus is resource-agnostic; only the interpretation of f changes.

Honesty about tradeoffs. Asymptotic notation intentionally discards information that sometimes matters in practice: the hidden constant c can be enormous (an O(n) algorithm with c = 10,000 can lose to an O(n²) algorithm with c = 1 for all realistic n), and n₀ can be large enough that "asymptotic" behavior never actually manifests on real inputs. The notation is a first filter, not a substitute for actual benchmarking, but it correctly predicts behavior in the limit, and for algorithms deployed at genuinely large and growing scale, the limit is what eventually dominates.

Let's prove three different claims about the same function, tracing every step of witness construction. Let ``` f(n) = 4n² + 30n + 100 ```

Claim 1: f(n) = O(n²). Bound each term for n ≥ 1: 30n ≤ 30n² and 100 ≤ 100n². So ``` f(n) ≤ 4n² + 30n² + 100n² = 134n² ``` Witness: c = 134, n₀ = 1. Check at n₀ = 1: f(1) = 4+30+100 = 134, and 134·1² = 134 — equality holds, so the inequality f(n) ≤ c·g(n) is satisfied (non-strict ≤ is fine). Check at n = 10: f(10) = 400+300+100 = 800, and 134·100 = 13,400 ≥ 800. ✓. A tighter, more typical witness: for n ≥ 30, note 30n ≤ n² and 100 ≤ n² (since n² ≥ 900), so f(n) ≤ 4n² + n² + n² = 6n². Witness: c = 6, n₀ = 30. Check at n = 30: f(30) = 3600+900+100 = 4600, and 6·900 = 5400 ≥ 4600. ✓. Both witnesses are valid — the definition only demands existence, not uniqueness or minimality.

Claim 2: f(n) = Ω(n²). Drop the positive lower-order terms (they only help): ``` f(n) = 4n² + 30n + 100 ≥ 4n² for all n ≥ 1 (since 30n+100 ≥ 0) ``` Witness: c = 4, n₀ = 1. Check at n = 1: f(1) = 134 ≥ 4·1 = 4. ✓. Check at n = 100: f(100) = 40,000+3,000+100 = 43,100 ≥ 4·10,000 = 40,000. ✓.

Claim 3: f(n) = Θ(n²). Immediate from Claims 1 and 2: using c₁ = 4, c₂ = 6, n₀ = 30 (taking the larger threshold to be safe, though n₀ = 30 alone suffices since it dominates n₀=1), ``` 4n² ≤ f(n) ≤ 6n² for all n ≥ 30 ``` which is exactly the Θ-definition with g(n) = n².

A trickier case — logarithms and bases. Consider f(n) = log₂(n) and g(n) = log₁₀(n). By the change-of-base formula, log₂(n) = log₁₀(n) / log₁₀(2), and log₁₀(2) ≈ 0.301 is a fixed positive constant. So ``` log₂(n) = (1/0.301) · log₁₀(n) ≈ 3.32 · log₁₀(n) ``` This gives both O and Ω with c ≈ 3.32 (and reciprocal for the other direction), n₀ = 1, proving log₂(n) = Θ(log₁₀(n)). This is why logarithm base is never written inside asymptotic notation — all logarithm bases differ only by a constant multiplicative factor, and Θ(log n) absorbs that ambiguity automatically.

A case where intuition fails — nested loops with a data-dependent bound. Consider code that, on input array of size n, runs an inner loop i times when processing the i-th element: ``` total_work(n) = 1 + 2 + 3 + ... + n = n(n+1)/2 ``` A common mistake is to eyeball this as "roughly n," confusing the number of outer iterations (n) with the total work. The correct closed form n(n+1)/2 = n²/2 + n/2 is a degree-2 polynomial, so by the polynomial technique above it is Θ(n²) — quadratic, not linear. Witnesses: for n ≥ 1, n²/2 + n/2 ≤ n²/2 + n²/2 = n² gives O(n²) with c=1, n₀=1; and n²/2 + n/2 ≥ n²/2 gives Ω(n²) with c = 1/2, n₀ = 1. So total_work(n) = Θ(n²), matching the familiar "triangular number" fact that sums of the first n integers grow quadratically.

Notice at n=10, f(n)=800 exceeds 6n²=600 — this is why n₀=30 was required for that particular witness; the O(n²) claim with c=6 only kicks in from n₀=30 onward, exactly as the definition demands.

The notation's mathematical origin lies not in computer science but in analytic number theory, decades before electronic computers existed, and its adoption into algorithm analysis came later through Donald Knuth's influential formalization.

Every performance guarantee in a systems paper, standard library, or database query planner is stated in this language. Database query optimizers choose between join algorithms by comparing their Θ bounds as table sizes scale into the billions of rows; a nested-loop join's Θ(n·m) cost versus a hash join's Θ(n+m) cost is exactly the kind of comparison this notation exists to make precise. Standard library documentation for languages like C++, Java, and Python routinely states complexity guarantees — "insertion at the back of a vector is O(1) amortized," "lookup in a hash map is O(1) expected, O(n) worst case" — using precisely these definitions, so that engineers can predict scaling behavior before writing a line of code. Compiler and hardware designers use asymptotic bounds when reasoning about cache-oblivious algorithms and parallel scheduling, since correctness of an asymptotic bound is stable across different machines even though the hidden constants differ. Theoretical computer science uses Ω lower bounds to prove that no algorithm can do better than a certain rate — the Ω(n log n) lower bound for comparison-based sorting is a foundational result that justifies why algorithms like merge sort and heap sort, at Θ(n log n), are asymptotically optimal within their model of computation. This same three-part vocabulary underlies the later study of the full hierarchy of growth rates (constant, logarithmic, linear, quadratic, exponential, and beyond) and gives the precise tools needed for counting operations in nested loops to actually assign a Θ bound to real code.

Ask the tutor: Can you show me how to prove that n! (factorial) is not O(2ⁿ) but n! is Ω(2ⁿ), and where the crossover happens?