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.