CODEWITHSUNDEEP
algorithm
Guest
Guest

Reputation: 3177

The running time of Insertion-Sort

In my book they have calculated the running time of insertion sort on an input of n. The algorithm is:

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           0     n-1
            sorted sequence A[1..j-1]
4.     i <- j - 1                         c4    n-1
5.     while i > 0 and A[i] > key         c5    sum_{j=2}^n t_j
6.         do A[i+1] <- A[i]              c6    sum_{j=2}^n (t_j-1)
7.         i <- i - 1                     c7    sum_{j=2}^n (t_j-1)
8.     A[i+1] <- key                      c8    n-1

And my problem is why the times=n in line 1? Why isn't it just n-1 times?

Upvotes: 0

Views: 1893

Answers (3)

Manu Shaurya
Manu Shaurya

Reputation: 35

On page 25 of CLRS "When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body." This means that exit condition will get executed one more time before exting the for or while loop.

Upvotes: 0

Rohit
Rohit

Reputation: 6613

Well in my perspective the extra 1 time cost in not of initialization in fact that is because after n-1 successful iteration control will come back to i<=(length(A)) condition and compares i with length of A. This 1 extra comparison cost in added to a loop.

This thing is explained on page no. 25 of Introduction to algorithm by Cormen.

Upvotes: 1

Marcelo Cantos
Marcelo Cantos

Reputation: 185862

Think about it in terms of a for loop in C:

for (int i = 2; i <= length(A); ++i) ...

This line is reached n times — once for the initialisation, and n - 1 times for the increment-and-test.

Upvotes: 0

Related Questions