O, Omega and Theta, defined properly

Three statements about how one function compares with another once n is large enough, each with two constants you have to be able to produce.

Exact operation counts are unwieldy and, worse, dishonest about their own precision: the 5 in $5n+3$ came from a decision about whether an addition and an assignment are one action or two. What is worth keeping is the shape. The tool for keeping only the shape is asymptotic notation, and it is built on a comparison you can watch happening.

Take an exact count, $f(n) = 3n^2 + 5n + 100$, and a candidate shape, $g(n) = n^2$. Multiply the shape by 4 and print both columns.

For small $n$ the 100 dominates and $f$ is far ahead. At $n = 13$, $f(13) = 507 + 65 + 100 = 672$ and $4 \times 169 = 676$, so the comparison flips, and it never flips back: the gap between $4n^2$ and $3n^2$ grows like $n^2$ while $5n + 100$ grows like $n$.

Two numbers came out of that: the multiplier 4, and the point 13 after which the claim holds. Those two numbers are the whole content of the definition.

Big O

Read the following as: $f$ grows no faster than $g$, apart from a constant factor, once $n$ is large enough.

To claim $f(n) = O(g(n))$ you must be able to produce a $c$ and an $n_0$ that work. The run above produced them: $c = 4$ and $n_0 = 13$. That is a complete proof that $3n^2 + 5n + 100 = O(n^2)$, provided you also check the inequality never fails again after 13, which the algebra does.

Here is that check written out. The claim $3n^2 + 5n + 100 \le 4n^2$ rearranges to $n^2 - 5n - 100 \ge 0$. The left side is increasing for $n \ge 3$, since raising $n$ by 1 adds $2n - 4$, which is positive there. At $n = 13$ it equals $169 - 65 - 100 = 4$, which is at least 0. Being non-negative at 13 and increasing after it, it stays non-negative for every $n \ge 13$.

Omega and Theta

Big O is an upper bound and says nothing about how small $f$ might be. The mirror image gives a lower bound.

For the same $f$, take $c = 3$ and $n_0 = 1$. Then $c\,g(n) = 3n^2$ and $f(n) - 3n^2 = 5n + 100$, which is positive for every $n \ge 1$. So $3n^2 + 5n + 100 = \Omega(n^2)$.

Combining the two results above with $c_1 = 3$, $c_2 = 4$ and $n_0 = 13$ gives $3n^2 + 5n + 100 = \Theta(n^2)$. Theta is the strongest of the three and the one to aim for, because it pins the growth rather than bounding it on one side.

It is equally important to be able to show a claim is false. Suppose someone asserts $n^2 = O(n)$. By the definition there would be fixed $c$ and $n_0$ with $n^2 \le c\,n$ for every $n \ge n_0$. Divide both sides by $n$, which is positive, to get $n \le c$ for every $n \ge n_0$. Now take $n$ to be whichever of $n_0$ and $c + 1$ is larger. That $n$ is at least $n_0$, so the inequality must apply to it, yet $n \ge c + 1 > c$. The two cannot both hold, so no such pair exists and the claim is false.

Little-o and little-omega

Big O allows $f$ and $g$ to grow at the same rate; $n^2 = O(n^2)$ is true. The lower-case versions demand a strict gap by changing one quantifier from there exists a c to for every c.

Here is the full argument that $5n = o(n^2)$. Fix any $c > 0$, however small. The requirement $5n < c\,n^2$ divides through by $n$ to give $5 < c\,n$, that is $n > 5/c$. So take $n_0$ to be any whole number larger than $5/c$; for $c = 0.001$ that is $n_0 = 5001$. Since a suitable $n_0$ exists for every $c$, the claim holds.

That is exactly what fails for $n^2$ against $n^2$: with $c = 0.5$ the requirement $n^2 < 0.5n^2$ is false for every $n$, so $n^2$ is not $o(n^2)$.

Little-omega, written with the lower-case Greek letter $\omega$, is the mirror image of little-o. It says $f$ grows strictly faster than $g$: whatever multiple of $g$ you name, however large, $f$ is past it from some point on and stays past it.

Here is the full argument that $n^2 = \omega(n)$, in the same shape as the little-o one. Fix any $c > 0$, however large. The requirement is $c\,n < n^2$. Divide both sides by $n$, which is positive for the values in question, to get $c < n$. So any $n_0$ that is itself larger than $c$ will do.

To name one, write $\lceil c \rceil$ for the ceiling of $c$, meaning $c$ rounded up to the nearest whole number, so $\lceil 2.3 \rceil = 3$ and $\lceil 4 \rceil = 4$. Then $n_0 = \lceil c \rceil + 1$ is a whole number strictly greater than $c$, and every $n \ge n_0$ is greater than $c$ as well. With $c = 1000$ that gives $n_0 = 1001$, and indeed $1000 \times 1001 = 1001000$ while $1001^2 = 1002001$, which is larger. A suitable $n_0$ exists for every $c$, so the claim holds.

And $n^2$ is not $\omega(n^2)$, for the same reason it is not $o(n^2)$: with $c = 2$ the requirement $2n^2 < n^2$ is false for every $n$. Little-omega, like little-o, refuses two functions that grow at the same rate.

When both functions are positive and the ratio settles down, a limit gives the answer faster than hunting for constants. If $f(n)/g(n)$ tends to a finite number that is not 0, then $f = \Theta(g)$. If it tends to 0, then $f = o(g)$, and in particular $f = O(g)$. If it grows without bound, then $f = \omega(g)$, and in particular $f = \Omega(g)$. The ratio $(3n^2+5n+100)/n^2 = 3 + 5/n + 100/n^2$ tends to 3, which confirms the Theta result in one line.