Big O

Everyone has probably heard of big-O.

When we say the running time of a sorting algorithm is , 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 is often a more precise way of saying the same thing.

Note that implies f(n) = O(g(n)).