My best guess is that the series $$ \sum_{i=1}^n i(n-(i-1)) $$ becomes $$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$ So the highest term is $n^2$ and there are $n$ terms. Does that mean its $O(n^3)$? That seems high. Intuitively, it seems like it should be closer to $O(n^2)$ but I can't find a way to bring it down mathematically.
-
1$\begingroup$ Try distributing $i$ in the summation then break it out into multiple summations. Solve them each independently. $\endgroup$– ryanApr 17, 2019 at 20:27
-
$\begingroup$ Agh, that was it. $\sum_{i=1}^n in + \sum_{i=1}^n -(i^2)-i $ is roughly $\frac{1}{2}n^3 - \frac{1}{3}n^3$ so still $O(n^3)$ $\endgroup$– ZayaApr 17, 2019 at 20:39
-
$\begingroup$ Your proof sketch for $O(n^3)$ is perfectly fine -- nothing more needed! Of course, we'd like $\Theta$ and for that you need to do more. $\endgroup$– RaphaelApr 17, 2019 at 20:54
3 Answers
We can lower bound the sum roughly by $$ \sum_{i=1}^n i(n+1-i) \geq \sum_{i=n/3}^{2n/3} (n/3)^2 \geq (n/3)^3. $$ This shows that it is $\Omega(n^3)$. Since each summand is at most $n^2$, the sum is also $O(n^3)$.
We can also compute the sum explicitly: $$ \sum_{i=1}^n i(n+1-i) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = (n+1) \frac{(n+1)n}{2} - \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(n+2)}{6}. $$ This expression equals the binomial coefficient $\binom{n+2}{3}$, and we can prove this bijectively. The binomial coefficient counts triples $(a,b,c)$ of elements satisfying $0 \leq a < b < c \leq n+1$. Notice that $1 \leq b \leq n$, and this corresponds to summation over $i$. Given $b$, we have $b$ choices for $a$ and $n+1-b$ choices for $c$.
$$\begin{align*} T(n)&=1n + 2(n-1) + 3(n-2) + ... + (n-1)2 + n\\ &=n(1+2+...+n)-(1+2+3+...+n)\\ &=(n-1)(1+2+3+...+n)\\ &=\Theta(n^3) \end{align*}$$
From ryan's comment, the summation, when you distribute $i$ and split it into more summations comes to $$\sum_{i=1}^n i(n-(i-1)) = \sum_{i=1}^n (i*n) + \sum_{i=1}^n (-(i^2)-i)$$ which is roughly $\frac{1}{2}n^3 - \frac{1}{3}n^3$ so the asymptotic bound is, in fact $O(n^3)$