3

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

Public Display Name
  • 233
  • 1
    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. – André Nicolas Feb 25 '14 at 20:43
  • 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$. – MPW Feb 25 '14 at 21:09

4 Answers4

2

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?

Yiorgos S. Smyrlis
  • 83,933
1

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

Hypergeometricx
  • 22,657
1

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.

John Hughes
  • 93,729
  • 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. – MPW Feb 25 '14 at 20:58
  • 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. – Hypergeometricx May 09 '17 at 17:22
  • 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. – John Hughes May 09 '17 at 22:25
0

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

  • 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. – Steven Stadnicki Feb 25 '14 at 23:07
  • The complexity for the loops all together is. I did misread the problem though: the complexity for the summation is $\Theta(n^4)$. –  Feb 25 '14 at 23:19