[Solved]: Sum number of times statement is executed in triple nested loop

Problem Detail: 

I have this code fragment:

for( i=0; i<n; i++ )     for( j=0; j<i; j++ )         for( k=0; k<j; k++ )             S; 

I need to find the number of times that S is executed in that code block. I plugged it into Wolfram Alpha but I am not sure if that is the right answer.

I want to be able to do the math in order to figure the answer out so can someone point me in the right direction?

Asked By : SlashTag

Answered By : ymbirtt

The Wolfram Alpha answer isn't quite correct - you're off by one in each sum - the loop will iterate over $\{1,...,n-1\}$, not $\{1,...,n\}$, though other than that your reasoning is sound. What you should be asking W/A for is:

$$ \sum^{n-1}_{i=0}\sum^{i-1}_{j=0}\sum^{j-1}_{k=0} 1 $$

If you break the sums down bit by bit it gets a little easier to swallow, just start at the innermost sum and work outwards. It's probably fairly obvious that $\sum^{j-1}_{k=0}1 = j$, which breaks the triple-sum down into $\sum^{n-1}_{i=0}\sum^{i-1}_{j=0}j$.

We have that $\sum^{i-1}_{j=0}j = \frac{1}{2}(i^2-i)$, so what was a double sum is now the difference of two sums, $\frac{1}{2}(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i)$.

The second term has already been worked out, and we have that $\sum^{n-1}_{i=0}i^2 = \frac{n(n-1)(2n-1)}{6}$. From there, you should be able to work out your answer;

\begin{align*} \frac{1}{2}\left(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i\right) &= \frac{1}{2}\left(\frac{n(n-1)(2n-1)}{6} - \frac{3n(n-1)}{6} \right)\\ &= \frac{1}{2}\left((2n-1)\frac{n(n-1)}{6} - 3\frac{n(n-1)}{6} \right)\\ &= \frac{n(n-1)(2n-4)}{12}\\ &= \frac{n(n-1)(n-2)}{6} \end{align*}

The results about the sum of the first $n-1$ numbers and the sum of the first $n-1$ square numbers are fairly standard ones - if you want some proofs of them then this page gives some nice arguments, though note that their sums end at $n$ and not $n-1$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16555