The running time of Insertion-Sort

In my book they have calculated the running time of insertion sort on an input of n. The algorithm is:

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           0     n-1
            sorted sequence A[1..j-1]
4.     i <- j - 1                         c4    n-1
5.     while i > 0 and A[i] > key         c5    sum_{j=2}^n t_j
6.         do A[i+1]开发者_运维知识库 <- A[i]              c6    sum_{j=2}^n (t_j-1)
7.         i <- i - 1                     c7    sum_{j=2}^n (t_j-1)
8.     A[i+1] <- key                      c8    n-1

And my problem is why the times=n in line 1? Why isn't it just n-1 times?

Well in my perspective the extra 1 time cost in not of initialization in fact that is because after n-1 successful iteration control will come back to i<=(length(A)) condition and compares i with length of A. This 1 extra comparison cost in added to a loop.

This thing is explained on page no. 25 of Introduction to algorithm by Cormen.

Think about it in terms of a for loop in C:

for (int i = 2; i <= length(A); ++i) ...

This line is reached n times — once for the initialisation, and n - 1 times for the increment-and-test.

On page 25 of CLRS "When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body." This means that exit condition will get executed one more time before exting the for or while loop.