1
$\begingroup$

I should calculate the count of key comparisons from an algorithm. I create the sum formula but now I don’t know, how to dissolve this.

The sum looks like: $ \eqalign{ \sum_{i=0}^{n-2}\sum_{i+1}^{n-1}1 } $

It would be nice, if someone could give me some tipps.

I knew that the second step must be: $ \sum_{i=0}^{n-2}(n-1-i) $

Greet.

  • 0
    Thanks guys! You helped me a lot! It is very simple...2012-01-23

3 Answers 3

2

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

2

Let us start from your expression $ \sum_{i=0}^{n-2}(n-1-i) $.

Look at this in detail, starting at $i=0$. When $i=0$, we have $n-1-i=n-1$. Look next at $i=1$. We get $n-1-i=n-2$. Continue. We get in turn $n-3$, $n-4$, and so on. At the end, when $i=n-2$, we have $n-1-i=1$.

So we are looking at the sum $(n-1)+(n-2)+\cdots+1,$ which will look more familiar if we write it as $1+2+\cdots+(n-1),$ the sum of the first $n-1$ positive integers. I assume you know the expression $\dfrac{m(m+1)}{2}$ for the sum of the first $m$ positive integers. The sum of the first $n-1$ positive integers is therefore $\frac{(n-1)(n)}{2}.$

Comment: The first step, which is to show that $\sum_{i+1}^{n-1} 1=n-1-i,$ is simple, but it is all too easy to get the wrong answer. We are adding together $1$'s. How many $1$'s? Just as many as there are integers from $i+1$ to $n-1$, inclusive. Maybe you can see immediately that there are $(n-1)-(i+1)+1$ such integers, which simplifies to $n-1-i$. But it is possible to get the count wrong by $1$. For concreteness, how many integers are there from $5$ to $7$, inclusive? By a direct count, we are talking about the numbers $5$, $6$, and $7$, so there are $3$ of them. Note that $7-5=2$, so simple subtraction undercounts by $1$.

0

It is near $\frac{n^2}{2}$. Also if your 'second step' is correct then you distribute that into three sums.