Search

0.3.5.1 Analysis

In the worst case each item inserted will be compared to the previous n-1 sorted items. This means the overall time complexity of the algorithm is:

1 + 2 + 3 + 4 + 5 + 6 ... + (n - 2) + (n - 1)

Rewritten as a sum this is:

$$\sum_{i=1}^{n-1} i$$

Which is a variant of the arithmetic series and reduces to:

$$\frac{1}{2} (n - 1)(n - 2)$$

By multiplying the above out it becomes clear that this is a O(n²)algorithm.

For best case data, sets that are already sorted, the Insertion sort runs in linear time. However for average data sets the efficiency is n².