algorithmcomplexity-theoryinsertion

Insertion sort analysis and summation notation

I am trying to understand the worst case analysis of Insertion sort and I have a problem with the math involved on slide 21 (ppt).

I understand the first formula:

Σ(j=1 to n) j=n(n+1)/2

But these I'm struggling with:

  1. Why is there a - 1 at the end?
    Σ(j=2 to n) j=n(n+1)/2-1
  2. Also, I don't understand this one:
    Σ(j=2 to n)(j-1) = n(n-1)/2
Solution

  • It's Gauss' trick to sum numbers from 1 to n:

    trick of gauss

    First formula

    However, the sum you want to compute starts at 2, not 1, that is why you have to subtract the first term (i.e. 1) from the formula:

    enter image description here

    Second formula

    Essentially, you compute the sum from 1 until (n-1). If you substitute n in Gauss' trick with n-1, you receive the second formula they use.

    You can also see this with an index transformation:

    enter image description here

    As you can see, I have adjusted the boundaries of the sum: Both the upper and lower bounds of the sum have been decreased by 1. Effectively, this deceases all terms in the sum by 1, to correct this, you have to add 1 to the term under the Σ: (j-1) + 1 = j.