13
$\begingroup$

Please consider the following triple-nested loop:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

The statement here is executed exactly $n(n+1)(n+2)\over6$ times. Could someone please explain how this formula was obtained? Thank you.

$\endgroup$
14
$\begingroup$

You can count the number of times the innermost for loop is executed by counting the number of triplets $(i,j,k)$ for which it is executed.

By the loop conditions we know that: $1 \leq i \leq j \leq k \leq n$ . We can reduce it to the following simple combinatorics problem.

  • Imagine $n+2$ boxes of red colour placed in an array from left to right.
  • Pick any 3 boxes from the $n+2$ boxes and paint them blue.
  • Form a triplet $(i,j,k)$ as follows:
    • $i$ = 1 + number of red coloured boxes to the left of first blue box.
    • $j$ = 1 + number of red coloured boxes to the left of second blue box.
    • $k$ = 1 + number of red coloured boxes to the left of third blue box.

So, we just need to count the number of ways of picking 3 boxes from $n+2$ boxes which is $n+2 \choose 3$.

$\endgroup$
  • 2
    $\begingroup$ Nice answer! The exact values of i, j, k are not important. We just need to know that any blue box can be placed in n possible positions and that their positions are bounded: 2nd comes always after the 1st and before the 3rd. $\endgroup$ – Dávid Natingga Aug 24 '12 at 14:54
  • $\begingroup$ @rizwanhudda Clear except for the $+2$ part in $n+2$. Can you explain it please? $n+3$ looks like the right number. $\endgroup$ – saadtaame Aug 27 '12 at 21:14
  • 1
    $\begingroup$ @saadtaame Yes. You can imagine having $n+3$ red boxes, but having freedom to choose 3 red boxes for painting blue from among "$n+2$ red boxes", as you cannot colour the first box as blue (Since $i \geq 1$) $\endgroup$ – rizwanhudda Aug 28 '12 at 18:16
3
$\begingroup$

for me, it's easier to notice the inner loop is executed $n-i$ times and the total number of executions in the inner loop is

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

this can be rewritten as $\sum_{j=0}^{n-i} n-i-j$ and is executed $n$ times, so the total number of executions is

$$ \sum_{i=0}^{n}\sum_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{6} $$

$\endgroup$
  • $\begingroup$ A challenge for you: Imagine you have a x-nested loop. According to the previous answer it would execute (n+x-1) choose x times. How would you compute your formula? $\endgroup$ – Dávid Natingga Aug 25 '12 at 2:17
  • $\begingroup$ luckily the OP didn't ask for x-nested! How does the other answer given expand to an x-nested loop? My answer should just get more sums going from 0 to n, 0 to n-i_1, 0 to n-i_2, ... , 0 to n-i_x. But I wouldn't know how to compute that. $\endgroup$ – andy mcevoy Aug 25 '12 at 7:23
  • 1
    $\begingroup$ The answer does not expand explicitly for a general x, but the reasoning process presented is easy to follow to x-nested loops. You just add more blue boxes. Neither do I know how I would compute those more sums. $\endgroup$ – Dávid Natingga Aug 25 '12 at 16:47

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.