1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Just start with n=1, and then do n=5 and n=10 and maybe some more and you should see the pattern to the equation for the number of times S is executed. $\endgroup$ – Guy Coder Oct 30 '13 at 0:08
2
$\begingroup$

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

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