title: "Big-O"

Big-O

Definition. $f(n) = O(g(n))$ means there exist a constant $c > 0$ and a threshold $n_0$ such that for every $n \geq n_0$, $f(n) \leq c \cdot g(n)$. The constant $c$ absorbs constant factors; the threshold $n_0$ absorbs small-input noise.

Proving a big-O claim means exhibiting witnesses $c$ and $n_0$; disproving one means negating the quantifiers: for every $c$ and $n_0$, some $n \geq n_0$ has $f(n) > c \cdot g(n)$. Defined in Lecture 9 and used throughout Unit 3. Siblings: Big-Omega (lower bound), Big-Theta (both directions), Little-o (strictly slower growth).