32

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

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
skystar7
  • 4,419
  • 11
  • 38
  • 41
  • 4
    http://mathoverflow.net/ – Pascal Thivent Mar 20 '10 at 17:11
  • 34
    ...is for research-level math questions only. – rjh Mar 20 '10 at 17:14
  • 15
    @PascalThivent: This question would be closed within seconds on mathoverflow. – sepp2k Mar 20 '10 at 17:15
  • 3
    @Stephan, that's the formula if the `N` is added on the left side. If it's not, one `N` is missing, so `2N` should be subtracted in the numerator. – Johannes Schaub - litb Mar 20 '10 at 17:16
  • 6
    Off-topic? - has algorithm analysis got nothing to do with programming? As Skystar says, the context is the analysis of an algorithm. –  Mar 20 '10 at 17:27
  • Because one quick way to add up numbers is to list the numbers ascending, then below that descending. Your realise all the time you're adding up N+1s (first pair 1,n, 2nd pair 2,n-1...) n times. Hence n*(n+1). You've actually summed all the numbers twice, so you half it to get the answer. –  Mar 20 '10 at 17:29
  • @rjh @sepp2k Sorry then, forget what I said. – Pascal Thivent Mar 20 '10 at 17:31
  • That's too basic for mathoverflow.net; it's considered A-level Maths/maybe GCSE here in the UK. –  Mar 20 '10 at 17:32
  • Stephan202: Only if the series starts at `n`. – Ken Mar 20 '10 at 17:40
  • 2
    Wow, I have serious objections to this being closed. – Steven Oxley Mar 20 '10 at 17:49
  • @litb, @Ken: You're right. I didn't observe that `N` itself isn't included (usually it is, with this problem statement). Doh! – Stephan202 Mar 20 '10 at 19:53
  • 1
    This is at it's heart a math question. Basically an algebraic identity. That doesn't kill it as a SO topic, but my personal benchmark for math questions belonging on SO is "Will the math be performed by a program *or* will the math be translated into code?" In this case the answer is "No.", so I would also vote for a close as off topic. YMMV. – dmckee --- ex-moderator kitten Mar 21 '10 at 07:03
  • Are you me?!?! I was just looking this up, you worded exactly as I was thinking about :D – yuudachi May 25 '10 at 02:54
  • https://math.stackexchange.com/ – phuclv May 06 '17 at 09:55

9 Answers9

46

(N-1) + (N-2) +...+ 2 + 1 is a sum of N-1 items. Now reorder the items so, that after the first comes the last, then the second, then the second to last, i.e. (N-1) + 1 + (N-2) + 2 +... The way the items are ordered now you can see that each of those pairs is equal to N (N-1+1 is N, N-2+2 is N). Since there are N-1 items, there are (N-1)/2 such pairs. So you're adding N (N-1)/2 times, so the total value is N*(N-1)/2.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
30

Start with the triangle...

    *
   **
  ***
 ****

representing 1+2+3+4 so far. Cut the triangle in half along one dimension...

     *
    **
  * **
 ** **

Rotate the smaller part 180 degrees, and stick it on top of the bigger part...

    **
    * 

     *
    **
    **
    **

Close the gap to get a rectangle.

At first sight this only works if the base of the rectangle has an even length - but if it has an odd length, you just cut the middle column in half - it still works with a half-unit-wide twice-as-tall (still integer area) strip on one side of your rectangle.

Whatever the base of the triangle, the width of your rectangle is (base / 2) and the height is (base + 1), giving ((base + 1) * base) / 2.

However, my base is your n-1, since the bubble sort compares a pair of items at a time, and therefore iterates over only (n-1) positions for the first loop.

9

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.

gius
  • 9,289
  • 3
  • 33
  • 62
7

See triangle numbers.

Viral Shah
  • 2,888
  • 2
  • 22
  • 25
  • 1
    Thanks I liked these techniques in explaining the proof of this formula especially technique number three, which can be found at http://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/ – skystar7 Mar 21 '10 at 11:36
5

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 kth pass, the kth largest element will be in the kth 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.

John Feminella
  • 303,634
  • 46
  • 339
  • 357
  • But it is also written that n(n - 1)/2 or O(n^2) or n^2. So square of n i.e square of 5 is 25. But n(n-1)/2 is 10. So how is this possible? – Harinder Mar 15 '15 at 08:08
  • @Harinder: "or O(n^2) or n^2 ...". No, O(n^2) == n^2 is not correct. `n^2 + 1,000,000` is also `O(n^2)` but is clearly not equal to `n^2`. – John Feminella Mar 15 '15 at 17:57
  • This is what I don't understand. For example look at this http://www.sparknotes.com/cs/sorting/bubble/section1.rhtml . It also says in the end that average and worst case are n^2 – Harinder Mar 15 '15 at 18:07
  • And also is this correct n(n - 1)/2 or O(n^2)?? If so how did it become O(n^2) – Harinder Mar 15 '15 at 18:09
  • @Harinder: You should ask a separate SO question. Comments aren't really good for answering things at length. – John Feminella Mar 15 '15 at 19:46
2

Sum of arithmetical progression

(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2

ShPavel
  • 962
  • 1
  • 10
  • 17
2

This is a pretty common proof. One way to prove this is to use mathematical induction. Here is a link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

John Kane
  • 4,383
  • 1
  • 24
  • 42
1

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.

martiert
  • 1,636
  • 2
  • 18
  • 23
0

Here's a proof by induction, considering N terms, but it's the same for N - 1:

For N = 0 the formula is obviously true.

Suppose 1 + 2 + 3 + ... + N = N(N + 1) / 2 is true for some natural N.

We'll prove 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 is also true by using our previous assumption:

1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1) = (N + 1)((N / 2) + 1) = (N + 1)(N + 2) / 2.

So the formula holds for all N.

M.Usman
  • 2,049
  • 22
  • 25
IVlad
  • 43,099
  • 13
  • 111
  • 179
  • 1
    "Suppose P(N) is true for all natural N". That's not a correct proof by induction. You're aiming to prove P(N) => P(N+1), so you should assume P(N) is true for *some* N. If you assume it for *all* N, then you beg the question. – Steve Jessop Mar 20 '10 at 17:35