Big O

Big O

• $T(n) = O(f(n))$
• if there exists a constant c, such that
• $T(n) \leqslant c \cdot f(n)$ for all $n \geqslant n_0$
• i.e. $T(n)$ is bound above $c \cdot f(n)$

Big Omega

• $T(n) = \Omega(f(n))$
• if $T(n) \geqslant c \cdot f(n)$ for all $n \geqslant n_0$ for any c

Theta

• $T(n) = \Theta(f(n))$
• if $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$
• (“sandwich” between $O$ and $\Omega$)

Links

• Plain English explanation of Big O (stackoverflow)

Sources

• Algorithms Design and Analysis Part 1 (coursera)