Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to find the expected number of swaps in a algorithm I'm working on. I've gotten to this point:

$E[S] =\sum_{j=1}^n\sum_{i=0}^{i<j} \frac{1}{2}$

I don't know how to reduce this further. The answer is supposed to be n(n-1)/4, but I don't know how to get there.

share|cite|improve this question
up vote 4 down vote accepted

What you have actually simplifies to $\frac14n(n+1)$:

$$\begin{align*} \sum_{j=1}^n\sum_{i=0}^{j-1}\frac12&=\frac12\sum_{j=1}^n\sum_{i=0}^{j-1}1\\ &=\frac12\sum_{j=1}^nj&&\text{since there are }j\text{ terms}\\ &=\frac12\cdot\frac{n(n+1)}2&&\text{by the well-known formula}\\ &=\frac{n(n+1)}4\;. \end{align*}$$

If the inner sum started at $i=1$, you’d have $$\frac12\sum_{j=1}^n(j-1)=\frac12\sum_{k=0}^{n-1}k=\frac12\cdot\frac{(n-1)n}2=\frac{n(n-1)}4\;.$$

share|cite|improve this answer
@Ryan Hurley: If you're wondering where you can find these properties, check out the wiki article: – apnorton Oct 31 '12 at 1:50
Thank you so much...this is perfect! – Ryan Hurley Oct 31 '12 at 1:53
@Ryan: You’re very welcome! – Brian M. Scott Oct 31 '12 at 2:01

Your Answer


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.