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)$?
Is this summation$O(n^2)$?
-
0I'm sorry! I had read 1 instead of j. – 2012-03-19
3 Answers
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.
-
0@JeffE: R$i$ght! I wrote this answer in a bit of a hurry, so I forgot to mention that. Thanks for the comment. – 2012-03-19
we know
$\sum_{i=b}^{n}{a}=(n-b+1)a$ (a and b are constant)
$\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)$
-
1yeah I go$t$ that I've correct that – 2012-03-19
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}$.