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:

But these I'm struggling with:

1. Why is there a - 1 at the end?
   
2. Also, I don't understand this one:
   

回答1:

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

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:

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:

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.

回答2:

Σ(j=2 to n) j=n(n+1)/2-1 starts at 2 instead of 1. So it's the same terms added together except the 1. So the sum is 1 less.

Σ(j=2 to n)(j-1) is the same terms added together as Σ(j=1 to n-1)(j). So to find its sum replace n with n-1 in the formula n(n+1)/2.