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 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|improve this question

1 Answer 1

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|improve this answer
    
@Ryan Hurley: If you're wondering where you can find these properties, check out the wiki article: en.wikipedia.org/wiki/Summation#Identities –  anorton 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

 
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.