計算插入排序的運行時間

Question

INSERTION_SORT (A) 

FOR j ← 2 TO length[A]   //c1*n 
    key ← A[j]     //c2*(n-1) 
    i ← j − 1     //c3*(n-1) 
    WHILE i > 0 and A[i] > key //c4*sigma(j=2 to n)of(tj) 
     A[i +1] ← A[i]   //c5*sigma(j=2 to n)of(tj-1) 
     i ← i − 1    //c6*sigma(j=2 to n)of(tj-1) 
    A[i + 1] ← key    //c7*(n-1) 

c1，c2，c3，c7總是有意義的。什麼沒有意義就是：

c4*sigma(j=2 to n)of(tj) becomes c4*sigma(j=2 to n)of(j) 

讓我們說什麼上面一行的意思是，在第4行的時間，我們正在計算大小5的陣列的最壞情況：

c4*(1+2+3+4) 

當在現實中，它是：

C4 *（（1）+（1 + 2）+（1 + 2 + 3）+（1 + 2 + 3 + 4））

我錯過了什麼？我知道這本書必須是正確的。

EDIT 秀逗，應該是：

c4*((1)+(1+1)+(1+1+1)+(1+1+1+1)) 
=c4*(1+2+3+4) 

Answer 1

但在第4行時間爲 2 + 3 + 4 + 5。第一時間（J = 2），它是2 （i = 1和i = 0）。第二次（j = 3），它是3（i = 2，i = 1，i = 0）...