When we compare algorithms, or counts like $2^{n}$ and $n!$, we care about what happens as $n$ grows, not about small cases or constant factors. Big-O notation makes that precise, and its definition is a nested quantifier statement. Logarithms, which grow slowly, sit at the bottom of the growth ladder.
Key idea
$f$ is $O(g)$ ("big-O of $g$") when there are constants $C$ and $k$ such that $|f(n)| \le C\,|g(n)|$ for every $n > k$. The common growth classes, from slowest to fastest, are $$\log n \ll \sqrt{n} \ll n \ll n\log n \ll n^{2} \ll n^{3} \ll 2^{n} \ll n!.$$
Why it works
Read the definition with its quantifiers: there exist $C$ and $k$ such that for all $n > k$… The "for all $n > k$" ignores any finite beginning, and the $C$ absorbs constant factors. So $100n$ is $O(n)$ (take $C = 100$), and $n^{2}$ is not $O(100n)$: whatever $C$ you pick, $n^{2} \le 100Cn$ fails once $n > 100C$. For the ladder, compare ratios: $n^{2}/n = n$ grows without bound, so $n^{2}$ is not $O(n)$, and the same argument works for each step up.
| $n$ | $\log_{2} n$ | $n\log_{2} n$ | $n^{2}$ | $2^{n}$ |
|---|---|---|---|---|
| $10$ | $3.3$ | $33$ | $100$ | $1{,}024$ |
| $100$ | $6.6$ | $664$ | $10^{4}$ | $\approx 10^{30}$ |
| $1{,}000$ | $10.0$ | $9{,}966$ | $10^{6}$ | $\approx 10^{301}$ |
Worked examples
Worked example: Finding witnesses
Show that $f(n) = 3n^{2} + 5n + 2$ is $O(n^{2})$.
- For $n \ge 1$: $5n \le 5n^{2}$ and $2 \le 2n^{2}$.
- So $f(n) \le 3n^{2} + 5n^{2} + 2n^{2} = 10n^{2}$.
- The witnesses $C = 10$, $k = 0$ (or $k = 1$) satisfy the definition.
Answer: $C = 10$ works for all $n \ge 1$.
Worked example: A constant cannot rescue it
Is $n^{2}$ $O(100n)$?
- Suppose $n^{2} \le C \cdot 100n$ for all $n > k$. Dividing by $n$: $n \le 100C$ for all $n > k$.
- That fails for any $n$ larger than both $k$ and $100C$.
- So no $C$ works: $n^{2}$ is not $O(100n)$, even though $100n$ is the larger one for every $n < 100$.
Answer: No
Worked example: The tightest class
Let $f(n) = 5n\log_{2} n + 100n + 7$. Which is the slowest-growing of $n$, $n\log n$, $n^{2}$ that $f$ is big-O of?
- The term $5n\log_{2} n$ eventually dominates: $100n \le 100\,n\log_{2} n$ once $\log_{2} n \ge 1$, and $7 \le 7n\log_{2} n$ too.
- So $f(n) \le 112\,n\log_{2} n$ for $n \ge 2$: $f$ is $O(n\log n)$. It is also $O(n^{2})$, but that is a looser statement. It is not $O(n)$, since $f(n)/n \ge 5\log_{2} n$ is unbounded.
Answer: $n\log n$
Common mistake
Judging growth from small values, or thinking a constant changes the class. At $n = 50$, $100n = 5{,}000$ beats $n^{2} = 2{,}500$, but that says nothing about large $n$. And $1000n$ and $n$ are both $O(n)$: big-O deliberately ignores constant factors. Check: look at the ratio $f(n)/g(n)$ for large $n$. If it stays bounded, $f$ is $O(g)$; if it grows without bound, it is not.