Big-O Notation and Asymptotic Analysis

Core Idea

Big-O notation gives an asymptotic upper bound on function growth: f(n) = O(g(n)) means there exist constants C > 0 and n₀ such that f(n) ≤ C·g(n) for all n ≥ n₀. Big-Ω provides a lower bound and Big-Θ a tight (matching) bound. Common complexity classes in increasing order of growth: O(1), O(log n), O(n), O(n log n), O(n²), O(nᵏ), O(2ⁿ), O(n!). Asymptotic analysis focuses on large-input behavior, deliberately ignoring constant factors that depend on hardware or implementation details.

How It's Best Learned

Prove O, Ω, and Θ relationships from the formal definition by explicitly finding C and n₀ for concrete examples. Plot several growth functions together on a graph to build visual intuition for which functions eventually dominate. Translate loop structures in pseudocode directly to their Big-Θ complexity.

Common Misconceptions

• Treating O(f) as an equality rather than an upper bound — 5n is O(n²) but is not Θ(n²).
• Keeping lower-order terms in the final answer — n² + 100n is Θ(n²), not Θ(n² + n).
• Confusing worst-case and average-case complexity when applying Big-O to an algorithm.

Explainer

When comparing algorithms, we rarely care about the exact number of operations — that depends on the processor, the compiler, and details of the input. What we care about is how the running time scales as the input size n grows. Big-O notation formalizes this by describing the long-run growth rate of a function while ignoring constant factors and lower-order terms.

The formal definition: f(n) = O(g(n)) means there exist positive constants C and n₀ such that f(n) ≤ C·g(n) for all n ≥ n₀. In plain English: eventually (past some threshold n₀), g(n) is an upper bound on f(n), up to a constant multiple. If an algorithm does 5n² + 3n + 100 operations, then past some n₀ we can find a constant C where C·n² covers all of that — the 3n and 100 become negligible compared to n² for large n. So we say the algorithm is O(n²).

A subtle but important point: Big-O is an upper bound, not an equality. Saying f = O(n²) does not mean f grows like n²; it means f grows *no faster than* n². A function that is O(n) is automatically also O(n²), O(n³), and O(2ⁿ) — all of those are valid (if weak) upper bounds. This is why Big-Θ is the more informative statement: f = Θ(g) says f is bounded *both above and below* by constant multiples of g. When you see Θ, you know the exact growth class; when you see O, you only know a ceiling.

The common complexity classes, from slowest to fastest growing, are: O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n), O(n²) (quadratic), O(nᵏ) (polynomial), O(2ⁿ) (exponential), O(n!) (factorial). This ordering matters practically: an O(n²) algorithm with n = 10,000 might take a second, while an O(2ⁿ) algorithm with n = 100 would take longer than the age of the universe. The gap between polynomial and exponential is not a matter of degree — it is the fundamental divide between tractable and intractable computation.

One more pitfall: Big-O describes a *class* of inputs, usually worst-case, but not always. When someone says "merge sort is O(n log n)", they typically mean its worst-case running time. But an algorithm can have different Big-O bounds for its best case, average case, and worst case. Quicksort, for example, is O(n log n) on average but O(n²) in the worst case. Always clarify which case is being analyzed when the distinction matters.