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)
サイズ5の配列の最悪のケースを計算しているとしましょう。上の行が言っているのは、4行目の時間が次のとおりであるということです。
c4*(1+2+3+4)
実際には次のようになります。
c4 *（（1）+（1 + 2）+（1 + 2 + 3）+（1 + 2 + 3 + 4））
私は何が欠けていますか？私はその本が正しくなければならないことを知っています。
編集 ねじ込み、次のようになります：
c4*((1)+(1+1)+(1+1+1)+(1+1+1+1))
=c4*(1+2+3+4)