Running Time of Insertion Sort

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I got following alg from a book:

InsertionSort(A)
1. Forj<--- 2 to length[A] ------------------- n times
2. Do key <--- A[j] -------------------- n-1 times (i.e. inside for loop)
3. i <---j – 1 -------------------- n-1 times (i.e. again inside for loop)
4. While I > 0 & A > key ------------------- (summation of j=2 to n) tj
5. Do A[I + 1]<---- A -------------------- (summation of j = 2 to n) tj -1 (i.e. inside while loop)
6. i <--- j-1 _____________(summation of j= 2 to n) tj -1 (i.e. inside while loop)
7. A[i+1] <--- key ______________ n-1

In the worst case when list is reverse sorted, we have
c1n +c2 (n-1) +c3(n-1) + c4(( n ( n+1) /2 )-1) + C5(n(n-1)/2)

I cant understand the fifth term. In my view it should be :
C5((n (n+1)/2) -2)
Can some body please guide me? I know there wont be any effect on running time but still I want to clear my concepts.
Zulfi.
 
Top