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 think my summation is in $O(n^2)$ but I am not sure how to show it. How should I show that this summation $$\sum_{i=1}^n\sum_{j=i}^n(j-i)$$ is in $O(n^2)$?

share|improve this question
2  
The result of the sum is zero. –  Mark Mar 19 '12 at 6:55
    
@Mark, that inner sum starts at $j=i$, not $j=1$. –  Gerry Myerson Mar 19 '12 at 8:52
    
I'm sorry! I had read 1 instead of j. –  Mark Mar 19 '12 at 12:20

3 Answers 3

up vote 4 down vote accepted

The summation counts the number of triples of integers $(i,j,k)$ satisfying $1 \le i < k < j+1 \le n+1$. (Fix $i,j$ and see that there are $j-i$ values of $k$ that can fit in between). So you should get $\binom{n+1}{3}$.

share|improve this answer
    
+1. Very elegant. –  Dejan Govc Mar 19 '12 at 13:52

we know

  1. $\sum_{i=b}^{n}{a}=(n-b+1)a$ (a and b are constant)

  2. $\sum_{i=a}^ni=\frac{(n-a+1)(n+a)}{2}$ (a is constant)

so $$\sum_{i=1}^n\sum_{j=i}^n(j-i)=\sum_{i=1}^n(\sum_{j=i}^n(j-i))=\sum_{i=1}^n(\sum_{j=i}^nj-\sum_{j=i}^ni))$$ $$=\sum_{i=1}^n(\sum_{j=i}^nj-(n-i+1)i)$$ $$=\sum_{i=1}^n(\sum_{j=i}^nj-(ni-i^2+i))$$ $$=\sum_{i=1}^n(\frac{(n-i+1)(n+i)}{2}-ni+i^2-i)$$ $$=\sum_{i=1}^n(\frac{n^2-i^2+n+i}{2}-ni+i^2-i)$$ $$=\frac12\sum_{i=1}^n[(n^2+n)+i(-1-2n)+i^2]$$ $$=\frac12[n(n^2+n)+(-1-2n)\frac{n(n+1)}{2}+\frac16n(n+1)(2n+1)]$$ $$=\frac{n^3-n}{6}$$

so it's in $O(n^3)$

share|improve this answer
1  
That inner sum starts at $j=i$, not $j=1$, and $\sum_{j=i}^nj\ne n(n+1)/2$. –  Gerry Myerson Mar 19 '12 at 9:04
1  
yeah I got that I've correct that –  Ehsan Mar 19 '12 at 9:07

The sum is not zero, since all the numbers are non-negative, and some of them strictly positive. But you can sum it explicitly. Hint: you can do it using the formulas $$\sum_{i=1}^ni=\frac12n(n+1) \\ \sum_{i=1}^ni^2=\frac16n(n+1)(2n+1)$$ and the fact $\sum$ is linear.

share|improve this answer
1  
So to answer the actual question: NO –  JeffE Mar 19 '12 at 9:24
    
@JeffE: Right! I wrote this answer in a bit of a hurry, so I forgot to mention that. Thanks for the comment. –  Dejan Govc Mar 19 '12 at 13:40

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.