Big-O Notation

Math for CS · Axiom Academy

Asymptotic upper bounds for algorithm analysis Big-O notation captures the idea of an asymptotic upper bound on a function's growth rate. Definition: We say if there exist positive constants and such that: In plain English: past some threshold , the function never exceeds . The growth of is bounded above by the growth of . Intuition: is like saying " grows no faster than ." It's an upper limit on how bad things can get. Proof: We need constants 0"> and such that for all . The technique: Bound each lower-order term by the dominant term (for sufficiently large ), then sum the coefficients to get . These are the complexity classes you will encounter most often, ordered from fastest to slowest growth: These simplification rules make Big-O analysis practical: Rule 2 — Drop lower-order terms: , . Rule 3 — Sum rule: If you do work followed by work, the total is . Rule 4 — Product rule: If you do work inside a loop that runs times, the total is . Example: A nested loop where the outer loop runs times and the inner loop runs times, with work inside: . Proof by contradiction: Suppose for all . Then for all , which is impossible since grows without bound. Since , we can choose . This is why the base of the logarithm doesn't matter in Big-O: all logarithms differ by a constant factor. Important: We always write without specifying the base, because for any bases 1"> .

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