Running Time of Insertion Sort

Discussion in 'Homework Help' started by zulfi100, Feb 10, 2016.

  1. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    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.
     
Loading...