If you want to make money online : Register now

# [Solved]: Understanding the time-complexity of Insertion Sort

, ,
Problem Detail:

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.

#### Answered By : Abhishek Bansal

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.