0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ hmm, i think i posted this to the wrong SE. How should I delete this? $\endgroup$ – Lost Sep 5 '14 at 22:15
  • $\begingroup$ this is actually an appropriate place for this question. $\endgroup$ – Newb Sep 6 '14 at 1:01
  • 1
    $\begingroup$ Don't use images as main content of your post. Not only is it lazy, it also makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – FrankW Sep 6 '14 at 10:41
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.