Big-O Notation

Big-O

One says that $f(x)=O(g(x))$ if there is some constant $M>0$ and $x_0$ such that $|f(x)|\le Mg(x)$ for all $x\ge x_0$.

Little-o

One says that $f(x)=o(g(x))$ if for all $ϵ>0$, there is some $x_0$ such that $|f(x)|\le ϵg(x)$ for all $x\ge x_0$.

Big-Omega (Hardy-Littlewood)

One says that $f(x)=\Omega (g(x))$ if

$$\underset{x\to \infty }{\mathrm{limsup}}\left|\frac{f(x)}{g(x)}\right|>0.$$

Big-Omega (Knuth)

One says that $f(x)=\Omega (g(x))$ if and only if $g(x)=O(f(x))$. Equivalently, there is some constant $M>0$ and $x_0$ such that $f(x)\ge M|g(x)|$ for all $x\ge x_0$.

Big-Theta

One says that $f(x)=\Theta (g(x))$ if $f(x)=O(g(x))$ and $f(x)=\Omega (g(x))$.