Asymptotic Notations

There are 3 main asymptotic notations to denote time complexity:

• Big-O (O)

• Big-Omega ($\Omega$)

• Big-Theta ($\Theta$)

We also have little-o (o) and little-omega ($\omega$)

Big-O (O)

Big-O is the most commonly used notation. It denotes the worst-case time complexity.

We say f(n) = O(g(n)) iff there exists some constant c>0, and $n_0$ such that f(n) <= c.g(n) for all n >= $n_0$

g(n) will be the upper-bound for f(n).

Big-Omega ($\Omega$)

We say f(n) = $\Omega$(g(n)) iff there exists some constant c>0, and $n_0$ such that f(n) >= c.g(n) for all n >= $n_0$

g(n) will be the lower-bound for f(n).

Big-Theta ($\Theta$)

We say f(n) = $\Theta$(g(n)) iff there exist some constants c$_1$ and c$_2$, and $n_0$ such that c$_1$.g(n) <= f(n) <= c$_2$.g(n) for all n >= $n_0$

g(n) will be both the upper and lower bound for f(n), for certain constants c$_1$ and c$_2$.

Little-o (o)

We say f(n) = o(g(n)) iff f(n) < c.g(n) for any c>0.

f is dominated by g asymptotically.

Little-omega ($\omega$)

We say f(n) = $\omega$(g(n)) iff f(n) > c.g(n) for any c>0.

g is dominated by f asymptotically.

Note the following relation between different n terms: