Question

Explain why building a list in sorted order is an O(n2) operation. You don’t have to derive it with mathematical formality, but at least explain why, mathematically, it’s O(n2).

Answer 1

By ignoring all the lower-order terms and constants, we would say sorting algorithm a is O(N2), which means that the growth rate of the work performed by algorithm a (the number of instructions it executes) is on the order of N2. This is called big O notation, and we use it to specify the complexity class of an algorithm.

We commonly express the cost of an algorithm as a function of the number N of elements that the algorithm acts on. The function gives us an estimate of the number of operations we have to perform in order to use the algorithm on N elements – it thus allows us to predict how the number of required operations will increase as N increases. We use a function which is an approximation of the exact function – we simplify it as much as possible, so that only the most important information is preserved.

For example, we know that when we use linear search on a list of N elements, on average we will have to search through half of the list before we find our item – so the number of operations we will have to perform is N/2. However, the most important thing is that the algorithm scales linearly – as N increases, the cost of the algorithm increases in proportion to N, not N² or N³. The constant factor of 1/2 is insignificant compared to the very large differences in cost between – for example – N and N², so we leave it out when we describe the cost of the algorithm.

Here are the best case, expected and worst case costs for the sorting and searching algorithms we have discussed so far:

Algorithm	Best case	Expected	Worst case
Selection sort	O(N2)	O(N2)	O(N2)
Merge sort	O(N log N)	O(N log N)	O(N log N)
Linear search	O(1)	O(N)	O(N)
Binary search	O(1)	O(log N)	O(log N)

What does O(1) mean? It means that the cost of an algorithm is constant, no matter what the value of N is. For both these search algorithms, the best case scenario happens when the first element to be tested is the correct element – then we only have to perform a single operation to find it.

Big O notation doesn't tell us everything that we need to know about the running time of an algorithm. For example, if two algorithms are O(N2), we don't know which will eventually become faster). And, if one algorithm is O(N) and another is O(N2), we don't know which will be faster for samll N.