ML Wiki

Big O

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

Big Omega

• [math]T(n) = \Omega(f(n))[/math]
• if [math]T(n) \geqslant c \cdot f(n)[/math] for all [math]n \geqslant n_0[/math] for any c

Theta

• [math]T(n) = \Theta(f(n))[/math]
• if [math]T(n) = O(f(n))[/math] and [math]T(n) = \Omega(f(n))[/math]
• ("sandwich" between [math]O[/math] and [math]\Omega[/math])

Links

• Plain English explanation of Big O (stackoverflow)

Sources

• Algorithms Design and Analysis Part 1 (coursera)