What is the proof of of N 1 N 2 N 3 1 N N 1 2

Question

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

User · Answer

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

User · Answer

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

User · Answer

See triangle numbers

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

Sum of arithmetical progression   A1 AN  2 N    1    N-1   2  N-1    N  N-1  2

[formula] What is the proof of of (N–1) + (N–2) + (N–3) + ... + 1= N*(N–1)/2

Examples related to formula

Examples related to proof