How is insertion sort a quadratic function?

In the worst case, insertion sort takes on the characteristic of a quadratic function, which is to say there is a squared term in the total runtime T(n). First, let’s determine the cost and number of times each instruction takes. Some notes:

  • a 1-based array
INSERTION-SORT(A)            cost  times   
for j = 2 to length[A]       c1    n
  do key <- A[j]             c2    (n-1)
    i <- j-1                 c3    (n-1)
    // a comment             0     (n-1)
    while i>0 and A[i]>key   c5    sum(j=2..n) t
      do A[i+1] <- A[i]      c6    sum(j=2..n) t-1    
        i <- i-1             c7    sum(j=2..n) t-1
    A[i] <- key              c8    (n-1)

Each loop runs one more time as part of its “loop check” to exit: the for loop runs from 2 to n, which is (n-1) times, plus one additional time to exit. Most loops I write start from 1 or 0 to n or (n-1), and those would run n times plus 1, or (n+1), times.

The sum(j=2..n) notation is summation from 2 to n, where t is the number of times per term: when j=2, t=2; when j=3, t=3; and so on. This summation includes the extra once of checking the loop exit, which is the i>0 check. When j=5, i initializes to 4 and takes on the values 3,2,1 and 0: the zero is the loop check.

If t is the number of times the loop runs, the instructions within the loop runs one less time, or (t-1); that’s why the while body runs (t-1) times.

The constants are numbered from c1 to c8 to represent a definite time to execute that instruction. We multiply this constant by the number of times to get a term to describe the subtotal cost; then T(n) is the sum of all these subtotals.

The shortcut of calculating the summation sum(j=2..n) t is n*(n+1)/2 – 1, which yields the n-squared. So in the worst case of a reversed list of numbers, insertion sort would take time-squared of the input size.