Big-O Notation

Discrete Math · Axiom Academy

Understanding asymptotic complexity: why constants and lower-order terms don't matter for large inputs, and how we classify algorithm efficiency. In plain English: f(n) grows no faster than g(n) (up to a constant multiple) for sufficiently large n. The constants c and n₀ exist to formalize "sufficiently large" and "up to a constant." Consider two algorithms: one takes 5n² steps, another takes 100n² steps. Both are O(n²) because the constant multiple doesn't change the fundamental growth rate. Similarly, lower-order terms vanish in importance: n² + 100n + 50 = O(n²) because the n² term dominates as n → ∞. 3. Big-Θ and Big-Ω: Tight Bounds Big-O gives an upper bound, but sometimes we need more precision: 4. The Complexity Class Hierarchy Common complexity classes, ordered from most efficient to least: O(log n) — Logarithmic (binary search) O(n log n) — Linearithmic (efficient sorting) O(n²) — Quadratic (nested loops) O(n³) — Cubic (triple nested loops) O(2ⁿ) — Exponential (recursive subsets) O(n!) — Factorial (all permutations)

This is the written version of the interactive lesson above. See the full Discrete Math course.