If you want to make money online : Register now

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

, , No Comments
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.

Thanks in advance.

Asked By : Lost

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29697

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback