DSA Insertion Sort Time Complexity

See this page for a general explanation of what time complexity is.

Insertion Sort Time Complexity

The worst case scenario for Insertion Sort is if the array is already sorted, but with the highest values first. That is because in such a scenario, every new value must "move through" the whole sorted part of the array.

These are the operations that are done by the Insertion Sort algorithm for the first elements:

• The 1st value is already in the correct position.
• The 2nd value must be compared and moved past the 1st value.
• The 3rd value must be compared and moved past two values.
• The 3rd value must be compared and moved past three values.
• And so on..

If we continue this pattern, we get the total number of operations for \(n\) values:

\[1+2+3+...+(n-1)\]

This is a well known series in mathematics that can be written like this:

\[ \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \]

For very large \(n\), the \(\frac{n^2}{2}\) term dominates, so we can simplify by removing the second term \(\frac{n}{2}\).

Using Big O notation, we get this time complexity for the Insertion Sort algorithm:

\[ O(\frac{n^2}{2}) = O(\frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

The time complexity can be displayed like this:

As you can see, the time used by Insertion Sort increases fast when the number of values is \(n\) increased.

Insertion Sort Simulation

Use the simulation below to see how the theoretical time complexity \(O(n^2)\) (red line) compares with the number of operations of actual Insertion Sorts.

For Insertion Sort, there is a big difference between best, average and worst case scenarios. You can see that by running the different simulations above.

The red line above represents the theoretical upper bound time complexity \(O(n^2)\), and the actual function in this case is \(1.07 \cdot n^2\).

Remember that a function \(f(n)\) is said to be \(O(g(n))\) if we have a positive constant \(C\) so that \(C \cdot g(n)>f(n)\).

In this case \(f(n)\) is the number of operations used by Insertion Sort, \(g(n)=n^2\) and \(C=1.07\).