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


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.