Understanding How Many Times Nested Loops Will Run

Question

I am trying to understand how many times the statement "x = x + 1" is executed in the code below, as a function of "n":

for (i=1; i<=n; i++)
  for (j=1; j<=i; j++)
    for (k=1; k<=j; k++)
       x = x + 1 ;

If I am not wrong the first loop is executed n times, and the second one n(n+1)/2 times, but on the third loop I get lost. That is, I can count to see how many times it will be executed, but I can't seem to find the formula or explain it in mathematical terms.

Can you?

By the way this is not homework or anything. I just found on a book and thought it was an interesting concept to explore.

Answer 1

Consider the loop for (i=1; i <= n; i++). It's trivial to see that this loops n times. We can draw this as:

* * * * *

Now, when you have two nested loops like that, your inner loop will loop n(n+1)/2 times. Notice how this forms a triangle, and in fact, numbers of this form are known as triangular numbers.

* * * * *
* * * *
* * *
* *
*

So if we extend this by another dimension, it would form a tetrahedron. Since I can't do 3D here, imagine each of these layered on top of each other.

* * * * *     * * * *     * * *     * *     *
* * * *       * * *       * *       *
* * *         * *         *
* *           *
*

These are known as the tetrahedral numbers, which are produced by this formula:

n(n+1)(n+2)
-----------
     6

You should be able to confirm that this is indeed the case with a small test program.

If we notice that 6 = 3!, it's not too hard to see how this pattern generalizes to higher dimensions:

n(n+1)(n+2)...(n+r-1)
---------------------
         r!

Here, r is the number of nested loops.

Answer 2

The 3rd inner loop is the same as the 2nd inner loop, but your n is a formula instead.

So, if your outer loop is n times...

and your 2nd loop is n(n+1)/2 times...

your 3rd loop is....

(n(n+1)/2)((n(n+1)/2)+1)/2

It's rather brute force and could definitely be simplified, but it's just algorithmic recursion.