# Is this summation$O(n^2)$?

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)$?

-
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

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}$.

-
+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)$

-
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.

-
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