Time Complexity

Insertion sort has a worst-case time complexity of O(n²).

This can be seen by using a simple graphical argument.

We will place a dot for each time unit taken by the algorithm.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i];
    int j;
    for (j = i; j > 0 && T[j - 1] > temp; --j) {
      T[j] = T[j - 1];
    }
    T[j] = temp;
  }
}

As the index “i” goes from 1 up to n – 1, we will represent the running time used for each value of i on its own line.

i = n-1:
...
i      :
...
i = 2  : 
i = 1  :

As the two declarations and the last assignment take a constant amount of time, let’s place a dot on each line to account for these.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i]; <----
    int j;           <----
    for (j = i; j > 0 && T[j - 1] > temp; --j) {
      T[j] = T[j - 1];
    }
    T[j] = temp;     <----
  }
}

i = n-1: *
...    : *
...    : *
...    : *
...    : *
i = 2  : *
i = 1  : *

For each value of i, it remains to add dots for the inner loop.

In the worst case, the inner loop makes j loop from i all the way down to 0, without stopping early due to the second stopping condition.

Therefore, it can have at most i iterations.

As each iteration takes constant time, we add “i” dots to each line.

i = n-1: * * * * * * * *
...    : * * * * * * *
...    : * * * * * *
...    : * * * * *
...    : * * * *
i = 2  : * * *
i = 1  : * *

The dots cover the entire upper-right half of the n by n matrix, give-or-take one dot.

This means that the running time in the worst case is approximately n × n / 2, which is Θ(n²).

Conclusion

Enjoyed our tutorial on Insertion Sort?

Cannot wait to understand more interesting algorithms and data structures?

Subscribe to the TrulyUnderstandingAlgorithms Youtube channel to stay up to date with our videos.