# 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: