Growth of Functions and Big-O

Big-O notation is simply a way to describe how fast an algorithm's work grows as you give it more to do. The "O" stands for "order," as in "order of growth": it sorts algorithms into rough classes like "grows like $n$" or "grows like $n^2$." That's what makes it useful, because all we're really asking is: when the input gets big, how badly does the work pile up? The definition looks dense, but it's just a few pieces: $f(n)$ (how many steps your program takes), $g(n)$ (a simple yardstick like $n^2$), $C$ (a fudge factor you're allowed to pick) and $n_0$ (the point after which you start paying attention). "$f = O(g)$" just means that once inputs are big enough, $f$ stays under some multiple of $g$. It's less scary than it looks; the rest of this lesson is learning to read and use that one sentence.

Why ignore constants? If one program takes $5n^2$ steps and another takes $n^2$, the first is five times slower, but a faster computer or a better compiler can make up that difference. What no hardware can fix is the shape of the growth. Double the input to an $n^2$ algorithm and it does four times the work, whatever the constant in front. Big-O keeps exactly that part and throws the rest away.

The hierarchy. Here are the common growth rates, from slowest-growing to fastest:

Each one eventually dwarfs everything to its left, no matter what constants you put in front. A $1000n$ algorithm loses to an $n^2$ one for small inputs, but once $n$ passes $1000$ the $n^2$ one is behind for good.

Rules of thumb. These all follow from the definition: you're allowed to pick any constant $C$, and you only care about large $n$.

• Drop constant factors: $5n^2 = O(n^2)$.
• Keep the fastest-growing term: $3n^2 + 100n + 7 = O(n^2)$.
• Nested loops multiply: a loop of $n$ steps inside another of $n$ steps is $O(n^2)$.
• The base of a logarithm doesn't matter: $\log_2 n$ and $\log_{10} n$ differ by a constant factor.

Related notation. Big-O is only an upper bound. $\Omega(g)$ is the matching lower bound (at least a constant times $g$, eventually), and $\Theta(g)$ means both at once: $f$ grows exactly like $g$.

A common mistake. Since $n = O(n^2)$ is true, it's tempting to read $f = O(g)$ as "$f$ grows like $g$." It doesn't say that. It only says $f$ grows no faster than $g$. If you want to say an algorithm really takes about $n^2$ steps, the right symbol is $\Theta(n^2)$.

Why it matters. At a billion operations per second, an $n^2$ algorithm on a million items takes about 17 minutes, an $n\log n$ one about 0.02 seconds, and a $2^n$ one wouldn't finish before the stars burn out, even for $n = 100$.

Engineers choose algorithms by their growth rates, because at the scale of millions of users the gap between n log n and n² is the gap between instant and unusable.