8.10. Big-O

As we saw one the last page, the exact way in which we count units of work in an algorithm is not as important as the degree to which the algorithm depends on the size of its input. An algorithm that always involves the same amount of work is more efficient than one where the work grows as a function of the input size (at least once we pass a certain problem size).

We can further divide the algorithms where work grows as a function of input size into categories based on what kind of function determines the growth. This is the idea behind what is known as Big-O classification: assigning algorithms to a class of function that describe their growth. Some common categories are Constant, Linear, Logarithmic and Quadratic; their relative growth are shown in the figure below.

../_images/CommonBigOs.svg

To write that an algorithm is in a particular class, we say that it is \(O(n)\) or \(O(log(n))\). Spoken, we would say something like: “Oh of n” or “Oh of log n”.

If the function that describes the work for an algorithm has multiple terms, we classify it only according to its fastest growning term. \(f(n) = n^2 + 2n\) would be considered Quadratic because for large values of n the \(n^2\) will dominate. Say n is 100: \(n^2 = 10,000\) and \(2n = 200\)… the extra 200 hardly even matters compared to the 10,000.