大O，$\Omega$, $\Theta$

Big O, $\Omega$, and $\Theta$ are ways to measure how a function grows asymptotically as $n$ gets large. Let's start with big O, since the other two are very easy to learn after mastering big O.

Definition. A function $f(n)$ is $O(g(n))$ if there exists a constant $c>0$ such that $f(n)<c\cdot g(n)$ holds for all sufficiently large $n$.

Essentially, this means that $f(n)=O(g(n))$ if $f$ is asymptotically bounded above by $g$ (up to a constant factor).

Essentially, for any function $f$, $O(f)$ returns a class of functions which in a loose sense increase at most as quickly as the function $f$ as $n$ approaches infinity. This is the main intuition behind the somewhat-tricky definition given at the beginning of the article. It doesn't matter how the two functions compare for small $n$ - we only care about large $n$.

We have analogous notation for dealing with functions which in a loose sense increase at least as quickly.

Definition. A function $f(n)$ is $\Omega(g(n))$ if there exists a constant $c>0$ such that $f(n)>c\cdot g(n)$ holds for all sufficiently large $n$.

In other words, $f(n)=\Omega(g(n))$ if $f$ is bounded below asymptotically by $g$.

Problem. Prove that $f(n)=O(g(n))$ if and only if $g(n)=\Omega(f(n))$.

Proof. If $f(n)=O(g(n))$, then $f(n)<c\cdot g(n)$ for some $c>0$, for all sufficiently large $n$. Therefore, $g(n)>\frac1c\cdot f(n)$ for all sufficiently large $n$, which means $g(n)$ is asymptotically greater than a constant factor times $f(n)$, where the constant factor is taken to be $\frac1c$. Thus, $g(n)=\Omega(f(n))$.

Conversely, if $g(n)=\Omega(f(n))$, then $g(n)>c\cdot f(n)$, so $f(n)<\frac1c\cdot g(n)$. So $f$ is bounded above by a constant multiple of $g$, so $f(n)=O(g(n))$.

Definition. A function $f(n)$ is $\Theta(g(n))$ if it is both $O(g(n))$ and $\Omega(g(n))$.

In other words, $f(n)=\Theta(g(n))$ if they grow at nearly the same rates as $n$ gets large.

Why is this under the CS topic? What does all this math stuff have to do with CS?

This is a very essential topic in CS and algorithm analysis. One of the first things we can ask about how good an algorithm is how it behaves as the size of the input changes. If an algorithm runs in $\Theta(\log n)$ (where $n$ is the input size), then we can double the input size and expect the computation time to increase linearly. If an algorithm runs in $O(n^2)$, then you can rest assured at night that it's faster than an algorithm that runs in $\Omega(2^n)$.

For example, the P vs. NP problem asks if all problems that can be verified in polynomial time can be solved in polynomial time.