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

2 Answers 2

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$
3
  • 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$ Aug 24, 2012 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$
    – mrk
    Aug 27, 2012 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$ Aug 28, 2012 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$
3
  • $\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$ Aug 25, 2012 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$ Aug 25, 2012 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$ Aug 25, 2012 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.