Big O

Everyone has probably heard of big-O.

When we say the running time of a sorting algorithm is O(n²), we are giving an asymptotic upper bound on the running time for all inputs of size n.

This is often what we want. However, saying that the running time is $\Theta(n^2)$ is often a more precise way of saying the same thing.

Note that $f(n) = \Theta(g(n))$ implies f(n) = O(g(n)).