## ‘Big O’ Notation

May 072018By making a series of assumptions and considering only “large” inputs, we can analyse how efficient an algorithm is without actually running it.
The result of this analysis is a *mathematical formula* called the complexity (or *time complexity*) of the algorithm.
For example, we derived the formula *n*^{2} for the selection sort algorithm.

Using standard notation, we would say that selection sort’s complexity is O(*n*^{2}), or that selection sort is an O(*n*^{2}) algorithm.

This formula says, very roughly, how much “work” the algorithm has to do as a function of *n,* which represents the “input size”.
In this post, we’ll see how to make sense of this formula, and how to derive it with as little algebra as possible.