Insert Sort Analysis and Summation

Question

I am trying to understand Insertion's worst sorting analysis, and I have a problem with the math involved in slide 21 (ppt) .

I understand the first formula:

But with this I struggle:

• Why is there - 1 at the end?
  
• Also, I do not understand this:
  

Answer 1

This is a gauss trick for summing numbers from 1 to n:

First formula

However, the amount you want to calculate starts with 2 , not 1 , so you must subtract the first term (i.e. 1) from the formula:

Second formula

Essentially, you calculate the sum from 1 to (n-1). If you replace n gauss trick by n-1 , you get the second formula that they use.

You can also see this with index conversion:

As you can see, I adjusted the boundaries of the sum: both the upper and lower boundaries of the sum were reduced by 1. Effectively, this reduces all terms in the sum by 1, to fix this, you have to add 1 to the term under Σ: (j-1) + 1 = j .

Answer 2

Σ(j=2 to n) j=n(n+1)/2-1 starts with 2 instead of 1. Thus, the same terms are combined together except 1. Thus, the sum is 1.

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