Why is the inner loop a summation?

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