Insertion sort time of the inner loop is considered a summation instead of just n or n-1 like the outer loop. That’s because the inner loop runs a certain number of times per outer loop:

j i values of i
-- -- ------------
2 1 1, 0
3 2 2, 1, 0
4 3 3, 2, 1, 0
5 4 4, 3, 2, 1, 0
6 5 5, 4, 3, 2, 1, 0
... ... ...
n n n

The total time is a summation of 2 + 3 + 4 + … + n for the inner loop. The zero value is the check that exits the loop. The outer for loop has a similar check, which is why it is n+1 time while its instructions are time n.

INSERTION-SORT(A)
for j <- 2 to length[A]
key <- A[j]
i <- j - 1
while i > 0 and A[i] > key
A[i+1] <- A[i]
i <- i - 1
A[i+1] <- key

### Like this:

Like Loading...

*Related*