8

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
Luuklag
  • 3,897
  • 11
  • 38
  • 57
Nikhil
  • 85
  • 1
  • 3

2 Answers2

10

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.

Luuklag
  • 3,897
  • 11
  • 38
  • 57
phant0m
  • 16,595
  • 5
  • 50
  • 82
  • @steve jessop: Thanks to you too. – Nikhil Sep 21 '12 at 19:44
  • why do we divide by 2? – KyelJmD Nov 12 '13 at 13:33
  • @KyelJmD If you sum the numbers 1 to 10, then you add `(1 + 10) + (2 + 9) + (3 + 8) + (4 + 7) + (5 + 6)`, that's five times 11. You divide by two, because when you have 10 numbers, and you group them in pairs of two, you end up with half as many pairs: 5. Does that help? – phant0m Nov 12 '13 at 20:18
  • but why do we have to (1 + 10) and etc? is this just a mathematical proof? but I am getting it little by little. – KyelJmD Nov 12 '13 at 23:13
  • 1
    @KyelJmD It's not a proof, I just reordered the numbers in the sum. Using a shorter example: `1 + 2 + 3 + 4 + 5 + 6`, reordering this, we have `1 + 6 + 2 + 5 + 3 + 4`, pairing, we have: `(1 + 6) + (2 + 5) + (3 + 4)`, evaluating the parens, we get: `7 + 7 + 7` which is `7*3` which is `7*6/2`, that's exctactly what the formula tells us. – phant0m Nov 13 '13 at 22:55
  • @Luuklag you a hero – ego2509 Mar 25 '21 at 15:33
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.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699