2
$\begingroup$

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

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.

1 Answers 1

5

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\;.$

  • 0
    @Ryan: You’re very welcome!2012-10-31