Time complexity of a triple-nested loop

Question

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.

The question Time complexity formula of nested loops might also be of interest. — Juho, Aug 24, 2012 at 7:48

Juho · Accepted Answer · 2012-08-24 07:30:04Z

14

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

Juho

22.4k7 gold badges60 silver badges115 bronze badges

answered Aug 24, 2012 at 7:06

rizwanhudda

5392 silver badges9 bronze badges

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, 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$
– rizwanhudda
Aug 28, 2012 at 18:16

Add a comment |

andy mcevoy · Accepted Answer · 2012-08-24 22:01:32Z

3

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

answered Aug 24, 2012 at 22:01

andy mcevoy

2131 silver badge5 bronze badges

$\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, 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$
– andy mcevoy
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$
– Dávid Natingga
Aug 25, 2012 at 16:47

Add a comment |

2 Answers 2