title: "Little-o"

Little-o

Definition. $f(n) = o(g(n))$ means: for every constant $c > 0$ there exists an $n_0$ such that for every $n \geq n_0$, $f(n) \leq c \cdot g(n)$.

Compare Big-O: the "there exists $c$" became "for every $c$" (Quantifier flip), so every constant multiple of $g$ eventually dominates $f$, making $f$ strictly slower-growing. Each entry of the growth-rate zoo is little-o of the next (Lecture 9); strict separations like this are what power the hierarchy theorems, which lie beyond this course.