next up previous contents index Search
Next: Improvements Up: 0.3.5 Insertion Sort Previous: 0.3.5 Insertion Sort 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:

\begin{displaymath}\sum_{i=1}^{n-1} i

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

\begin{displaymath}\frac{1}{2} (n - 1)(n - 2)

By multiplying the above out it becomes clear that this is a O(n2)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 n2.

Scott Gasch