3
$\begingroup$

$$\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} i + j + k$$

The question is looking for a $\Theta(g(n))$ function to represent this summation, but I am uncertain how to go about computing triple summations.

P.S. This is not homework. It was actually an exam question for a class that I missed today.

$\endgroup$
  • 1
    $\begingroup$ If it is a $\Theta$ question, the answer is immediate: Sum once we get a square plus lower terms, sum twice we get a cube plus lower terms, sum $3$ times $\dots$. As for explicit answer, either use the geometry, or do the sums one at a time, using "known" formulas for $\sum_1^{m} k$, $\sum_1^m k^2$ and $\sum_1^m k^3$. That is quite tedious. $\endgroup$ – André Nicolas Feb 25 '14 at 20:43
  • $\begingroup$ See my comment below. It looks like the answer is $\boxed{n(n-1)^2(n-2)/4}$. I checked and this matches for $n=1,2,3$. The sums are mostly empty until you reach $n=3$, when it becomes simply a single sum $2+1+0=3$. $\endgroup$ – MPW Feb 25 '14 at 21:09
2
$\begingroup$

Hint. \begin{align} \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}( i + j + k) &= \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}i+ \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}j+ \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1}k \\ &= \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} ij+\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} j^2+ \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \frac{j(j-1)}{2} \\ &= \sum_{i=0}^{n-1} \frac{i^2(i-1)}{2}+\sum_{i=0}^{n-1} \frac{i(i-1)(2i-1)}{6}+ \sum_{i=0}^{n-1} \frac{i(i-1)(i-2)}{6} \\ &= \sum_{i=0}^{n-1} \frac{i^2(i-1)}{2}+\sum_{i=0}^{n-1} \frac{i(i-1)(3i-3)}{6} =\sum_{i=0}^{n-1}\frac{i(i-1)(2i-1)}{2}. \end{align} Can you continue after this?

$\endgroup$
1
$\begingroup$

Split it into this:

$$ S = \sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j-1} i + j + k = \sum_{i=0}^{n-1} \left( i + \left(\sum_{j=0}^{i-1} \left(j + \sum_{k=0}^{j-1} k\right) \right) \right) $$ The innermost sum is $j(j-1)/2$; add $j$ to that to get $j(j+1)/2$. Factor out the $1/2$ and get $$ S = \frac{1}{2} \sum_{i=0}^{n-1} \left( i + \left(\sum_{j=0}^{i-1} j^2 + j \right) \right) $$ Now apply the summation rule for $j^2$ and for $j$ in the same way, and then the summation rules for $i^3, i^2,$ and $i$, and you'll get an answer.

$\endgroup$
  • $\begingroup$ You beat me to it. +1 for you. I got $\boxed{n(n-1)^2(n-2)/4}$ in the end, but I haven't checked my work. I'll try plugging in a few test values and computing by hand. $\endgroup$ – MPW Feb 25 '14 at 20:58
  • $\begingroup$ In the summand, each of $i,j,k$ must be triple-summed (see solution by Yiorgos). However, this is not the case in the rightmost expression of the first equation line in the solution above. $\endgroup$ – hypergeometric May 9 '17 at 17:22
  • $\begingroup$ You're correct. But the error doesn't affect the big-theta class of the answer, so I'm not going to take the time to fix it, esp since Yiorgos already did it rather nicely. $\endgroup$ – John Hughes May 9 '17 at 22:25
0
$\begingroup$

This represents three loops nested together. And a simple loop has order $\Theta(n)$. And also in general $\Theta(f\circ g)=\Theta(f)\Theta(g)$. And if you have a loop that depends arithmetically on an outer loop, then the order of the inner loop is the same as the outer loop. Thus in your case you have that the time complexity is $\Theta(n^3)$.

$\endgroup$
  • $\begingroup$ This has a few problems - while the intention is good, it's lacking a lot of precision as to, for instance, what a 'simple loop' is. And it's not true that the complexity of the result is $\Theta(n^3)$; see other answers. $\endgroup$ – Steven Stadnicki Feb 25 '14 at 23:07
  • $\begingroup$ The complexity for the loops all together is. I did misread the problem though: the complexity for the summation is $\Theta(n^4)$. $\endgroup$ – Robert Wolfe Feb 25 '14 at 23:19
0
$\begingroup$

(New Solution)

This solution is much neater than the earlier solution (see below). $$\begin{align} S &=\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\sum_{k=0}^{j-1}i+j+k=\color{lightgrey}{\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=0}^{j-1}i+j+k}\tag{1}\\ &=\sum_{r=0}^{n-1}\sum_{s=n-i\\\;=r+1}^{n-1}\sum_{t=n-j\\\;=s+1}^{n-1}3(n-1)-(r+s+t) &&\scriptsize{r=n-1-i\\s=n-1-j\\ t=n-1-k}\\ &=\sum_{t=2}^{n-1}\sum_{s=1}^{n-1}\sum_{r=0}^{n-1}3(n-1)-(t+s+r) &&\scriptsize 0\le r<s<t\le n-1\\ &=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=1}^{j-1}3(n-1)-(i+j+k)\tag{2}\\ &=\frac 32(n-1)\sum_{i=2}^{n-1}\sum_{j=2}^{n-1}\sum_{k=0}^{n-1}1 &&\frac {(1)+(2)}2\\ &=\frac 32(n-1)\sum_{i=2}^{n-1}\sum_{j=2}^{n-1}\binom j1\\ &=\frac 32(n-1)\sum_{i=2}^{n-1}\binom i2\\ &=\color{red}{\frac 32(n-1)\binom n3}\\ &=\color{red}{\frac {n(n-1)^2(n-2)}4}\\ &=\color{red}{\binom {n-1}2\binom n2} \end{align}$$


(Earlier solution below)

This solution arrives at the solution in the form of the product of two sums of integers.

$$\begin{align} \sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\sum_{k=0}^{j-1}(i+j+k) &=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{k=0}^{j-1}(i+j+k)\\ &=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\sum_{s=1}^{j}(i+2j-s) &&(s=j-k)\\ &=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}\sum_{j=s}^{i-1}(i+2j-s) &&(1\le s\le j\le i-1)\\ &\color{lightgrey}{=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}(i-s)(i-s)+2\cdot \frac {i-s}2(s+\overline{i-1})} &&\color{lightgrey}{\text{(number of steps=$i-s$)}}\\ &=\sum_{i=2}^{n-1}\sum_{s=1}^{i-1}(i-s)(i+\overline{i-1})\\ &=\sum_{i=2}^{n-1}\sum_{r=1}^{i-1}r(i+\overline{i-1}) &&(r=i-s)\\ &=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}(i+\overline{i-1}) &&(1\le r<i\le n-1)\\ &=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}(i-1)\\ &=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{r=1}^{n-2}r\sum_{i=r}^{n-2}i\\ &=\sum_{r=1}^{n-2}r\sum_{i=r+1}^{n-1}i+\sum_{i=1}^{n-2}i\sum_{r=1}^{i}r &&(1\leq r\le i\le n-2)\\ &=\sum_{i=1}^{n-2}i\sum_{r=i+1}^{n-1}r+\sum_{i=1}^{n-2}i\sum_{r=1}^{i}r\\ &=\sum_{i=1}^{n-2}i\left(\sum_{r=1}^i r+\sum_{r=i+1}^{n-1}r\right)\\ &=\sum_{i=1}^{n-2}i\sum_{r=1}^{n-1}r\\ &=\color{red}{\binom {n-1}2\binom n2}\\ &=\color{red}{\frac 14n(n-1)^2(n-2)} \end{align}$$

$\endgroup$

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.