Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm writing some software that takes a group of users and compares each user with every other user in the group. I need to display the amount of comparisons needed for a countdown type feature.

For example, this group [1,2,3,4,5] would be analysed like this:

1-2, 1-3, 1-4, 1-5
2-3, 2-4, 2-5
3-4, 3-5
4-5

By creating little diagrams like this I've figured out the pattern which is as follows:

Users - Comparisons
2     -   1
3     -   3 (+2)
4     -   6 (+3)
5     -   10 (+4)
6     -   15 (+5)
7     -   21 (+6)
8     -   28 (+7)
9     -   36 (+8)

I need to be able to take any number of users, and calculate how many comparisons it will take to compare every user with every other user.

Can someone please tell me what the formula for this is?

share|improve this question
    
MJD is right, of course, but... What kind of comparison are you doing? Maybe a sort would do? If there are many users, it can be faster, depending on your needs. –  Jean-Claude Arbaut May 2 at 15:25
2  
You're looking for the cardinal of the complete graph $K_n$, which is actually $\frac{n(n-1)}{2}$ –  Yann Hamdaoui May 2 at 15:25
    
Wow, so simple, thanks MJD! And Jean, it's nothing to do with sorting, that would be about as simple as myList.Sort(myComparer). –  Owen May 2 at 15:28
1  
This is the handshake problem. mathworld.wolfram.com/HandshakeProblem.html –  Shoe May 2 at 16:07
1  
@Bobson I'm not sure BigO has much to do with this question. There seems to be no mention of asymptotic behaviour at all here. He simply wants a closed form for this recurrence relation (which I'm surprised nobody has pointed out, are the triangular numbers) –  Cruncher May 2 at 17:25

7 Answers 7

up vote 13 down vote accepted

The sum of $0+\cdots + n-1$ is $$\frac12(n-1)n.$$

Here $n$ is the number of users; there are 0 comparisons needed for the first user alone, 1 for the second user (to compare them to the first), 2 for the third user, and so on, up to the $n$th user who must be compared with the $n-1$ previous users.

For example, for $9$ people you are adding up $0+1+2+3+4+5+6+7+8$, which is equal to $$\frac12\cdot 8\cdot 9= \frac{72}{2} = 36$$ and for $10$ people you may compute $$\frac12\cdot9\cdot10 = \frac{90}2 = 45.$$

share|improve this answer

You want to know how many ways there are to choose $2$ users from a set of $n$ users.

Generally, the number of ways to choose $k$ elements from a set of order $n$ (that is, all elements in the set are distinct) is denoted by $$ \binom{n}{k} $$

and is equivalent to $$ \frac{n!}{(n-k)!k!} $$

In the case of $k=2$ the latter equals to $$ \frac{n!}{(n-2)!2!}=\frac{n(n-1)}{2} $$

which is also the sum of $1+2+...+n-1$.

For more information see Binomial coefficient and Arithmetic progression

share|improve this answer

The following way to getting the solution is beautiful and said to have been found by young Gauss in school. The idea is that the order of adding $1+2+\cdots+n=S_n$ does not change the value of the sum. Therefore:

$$1 + 2 + \ldots + (n-1) + n=S_n$$ $$n + (n-1) + \ldots + 2 + 1=S_n$$

Adding the two equations term by term gives

$$(n+1)+(n+1)+\ldots+(n+1)=2S_n$$

so $n(n+1)=2S_n$. For $n$ persons, there are $S_{n-1}$ possibilities, as others answers have shown already nicely.

share|improve this answer

The discrete sum up to a finite value $N$ is given by,

$$\sum_{n=1}^{N} n = \frac{1}{2}N(N+1)$$

Proof:

The proof by induction roughly boils down to:

$$S_N = 1+ 2 +\dots+N$$

$$S_{N+1}= 1+ 2 + \dots + N + (N+1) = \underbrace{\frac{1}{2}N(N+1)}_{S_N} + (N+1)$$

assuming that the induction hypothesis is true. The right hand side:

$$\frac{N(N+1)}{2}+(N+1)=\frac{(N+1)(N+2)}{2}$$

which is precisely the induction hypothesis applied to $S_{N+1}$.


Just for your own curiosity, the case $N=\infty$ is of course divergent. However, with the use of the zeta function, it may be regularized to yield,

$$\sum_{n=1}^{\infty}n = \zeta(-1)=-\frac{1}{12}$$

share|improve this answer

$$N=2:\ 1 + 2 = (1 + 2) = 1\times3$$

$$N=4:\ 1 + 2 + 3 + 4 = (1 + 4) + (2 + 3) = 2\times5$$

$$N=6:\ 1 + 2 + 3 + 4 + 5 + 6 = (1 + 6) + (2 + 5) + (3 + 4) = 3\times7$$

$$N=8:\ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8= (1 + 8) + (2 + 7) + (3 + 6)+ (4 + 5) = 4\times9$$

More generally, $N/2\times(N + 1)$.

For odd $N$, sum the $N-1$ first terms (using the even formula) together with $N$, giving $(N-1)/2\times N+N=N\times(N+1)/2$.

share|improve this answer
    
Except that you should never count yourself, so you should be starting at 0 instead of 1. You'll have to take your result and subtract N from it. So for N = 2 you take your 1 x 3 = 3 - N = 3 - 2 = 1, which matches the table listed by OP. –  corsiKa May 2 at 17:31
    
@corsiKa: the formula explicitly shows the sum from 1 to $N$ inclusive (triangular numbers) and is perfectly correct. It is NOT the formula for the number of comparisons between $N$ users. –  Yves Daoust May 2 at 21:38
    
I think you're missing my point. I'm not saying your math is wrong at all. I'm saying it doesn't match what the OP is looking for. If you are not giving he formula for the number of comparisons between N users, then you aren't answering the OPs question, which makes this an incorrect answer for this question. –  corsiKa May 2 at 21:44
    
The sum must be taken from $1$ to $Users-1$ inclusive. –  Yves Daoust May 2 at 21:51
    
Yes. And the sum 1 + 2 + ... n-1 is n*(n-1)/2 while your answer says n*(n+1)/2. –  corsiKa May 2 at 22:28

Here is another way to find the sum of the first $n$ squares that generalizes to sums of higher powers.

$(k+1)^2 - k^2 = 2k+1$

$\sum_{k=1}^n ( (k+1)^2 - k^2 ) = \sum_{k=1}^n (2k+1)$

$(n+1)^2 - 1^2 = 2 \sum_{k=1}^n k + n$

$\sum_{k=1}^n k = \frac{ (n+1)^2 - 1 - n }{2} = \frac{n^2+n}{2}$

share|improve this answer

This is kind of a pseudo code:

Say you have n number of people, and you labeled them.

for i in (1,2,3,...,n), person i need to compare with all the people who has a number larger (strictly), so person i need to compare (n-i) times.

so adding up would be (n-1) + (n-2) + ... + 3 + 2 + 1...

which would be the sum from 1 to (n-1)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.