1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Try distributing $i$ in the summation then break it out into multiple summations. Solve them each independently. $\endgroup$ – ryan Apr 17 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$ – Zaya Apr 17 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$ – Raphael Apr 17 at 20:54
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

$$\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*}$$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you edit it so it's omega $n^3$ too? $\endgroup$ – lox Apr 17 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.