What is the proof of of (N–1) + (N–2) + (N–3) + …

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 10 years ago.

I got this formula from a data structure book in the bubble sort algorithm.

I know that we are (n-1) * (n times), but why the division by 2?

Can anyone please explain this to me or give the detailed proof for it.

Thank you

Answer 1

I know that we are (n-1) * (n times), but why the division by 2?

It's only (n - 1) * n if you use a naive bubblesort. You can get a significant savings if you notice the following:

• After each compare-and-swap, the largest element you've encountered will be in the last spot you were at.

• After the first pass, the largest element will be in the last position; after the k^th pass, the k^th largest element will be in the k^th last position.

Thus you don't have to sort the whole thing every time: you only need to sort n - 2 elements the second time through, n - 3 elements the third time, and so on. That means that the total number of compare/swaps you have to do is (n - 1) + (n - 2) + .... This is an arithmetic series, and the equation for the total number of times is (n - 1)*n / 2.

Example: if the size of the list is N = 5, then you do 4 + 3 + 2 + 1 = 10 swaps -- and notice that 10 is the same as 4 * 5 / 2.

Answer 2

Assume n=2. Then we have 2-1 = 1 on the left side and 2*1/2 = 1 on the right side.

Denote f(n) = (n-1)+(n-2)+(n-3)+...+1

Now assume we have tested up to n=k. Then we have to test for n=k+1.

on the left side we have k+(k-1)+(k-2)+...+1, so it's f(k)+k

On the right side we then have (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/2 = kf(k)

So this have to hold for every k, and this concludes the proof.

Answer 3

Try to make pairs of numbers from the set. The first + the last; the second + the one before last. It means n-1 + 1; n-2 + 2. The result is always n. And since you are adding two numbers together, there are only (n-1)/2 pairs that can be made from (n-1) numbers.

So it is like (N-1)/2 * N.