Understanding the time-complexity of Insertion Sort

Question

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below).

INSERTION-SORT(A)                         cost     times
1  for j <- 2 to length[A]                c1       n
2      DO key <- A[j]                     c2       n - 1
3         ▷ Insert A[j] into the sorted
          ▷          sequence A[i..j-1]   0        n - 1
4         i <- j-1                        c4       n - 1
5         while i > 0 and A[i] > key      c5       sum_{j=2}^2 t_j
6            do a[i+1]<-A[i]              c6       sum_{j=2}^2 (t_j-1)
7                i <- i-1                 c7       sum_{j=2}^2 (t_j-1)
8         A[i+1] <- key                   c8       n - 1

The algorithm above shows the times that each statement is executed. But wait, why is line 1 executed n times?

Shouldn't line 1 be executed n-1 times since insertion sort starts making comparisons at the second element at the list.

Thanks in advance.

Answer 1

As I see this, it is clear that the array is indexed from 1 to length[A] instead of the usual 0 to length[A}-1.

The first statement is executed n times. It is just that (n-1) times it enters the loop and the last time n'th time when j > length[A] it exits from the loop.

Hence it is correctly mentioned that the internal statements get executed n-1 times.