Andrew Jesaitis ::

the attic of my mind

Number of iterations of nested for loops

The Problem:

Recently in my numerical methods class, I recieved the following question:

Find the generalized solution for “sum” in the following code:

int sum = 0;
for (int i= 1; i <= n; i++){
    for (int j= 1; j <= i; j++){
	for (int k= 1; k <= j; k++){
	    sum++;
	}
    }
}



Interestingly, there is very little on Stackoverflow about finding the number of iterations of nested for loops. To me this means the answer has little practical importance to 99.9% of code out there. You know what that means? It makes the questions a great math problem (i.e. not practical and deceptively simple).

The algebraic solution is pretty straightforward. But, here's what I've found about algebraic solutions from majoring in math. Most people reguritating the formula actually don't understand it. I mean really understand the "why" of the solution. There's that 1% of math geniuses who get it from straight algebra, but most of us (myself included) don't automatically have an intuitive feel of what the equation is actually saying. So here's the algebraic solution:

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

I actually didn't derive the solution from a summation of a summation first, however. I did something cooler.

Check this out:

We know that one for loop runs n times.

And we can figure out quickly how many times two nested for loops run.

for (int i= 1; i <= n; i++){
    for (int j= 1; j <= i; j++){
        sum++;
   }
}


This is just the sum of:

1+2+3+4+...+n=\frac{n(n+1)}{2}

And you probably remember that neat little graphical proof of this summation. We make a triangle with 1 X in the first row, 2 X's in the second, and so on. Then we turn it into a rectangle using O's. For example:

XOOOO
XXOOO
XXXOO
XXXXO

Now the key thing to note is that we added an "O" to the bottom row. Thus the "area" (or number of elements) of the rectangle is:

n(n+1)

And the number of X's (what we are after) is half that:

\frac{n(n+1)}{2}

Okay now let's extend that idea to 3 nested loops. We can now think of the trangle as being made of numbers representing the depth in the z-dimension at that point. So our triangle becomes:

1
21
321
4321

Now imagine if what this would look like if we drew it in 3-D with X's. It'd look like a triangular pyramid!! Now what would the dimension of the pyramid be if we are calculating the volume similarly to how we calulated the area of the triangle. Well we know it is n units tall in the y-dimension, and (n+1) units wide in the x-dimension.

We just need the z-dimension. Well (n+1) is a good guess, but we actually have to add two triangles to make our shape into a rectangular prism (one in the z-dimension and one in the y-dimension). Then we are going to cut off parts of it to get our triangular pyramid (check out http://nrich.maths.org/1408 for a good graphical derivation of the volume of a triangular pyramid). So we have a triangular pyramid with dimension (n)x(n+1)x(n+2) and using that volume formula you learned in 7th grade we have:

\frac{n(n+1)(n+2)}{6}

Et, Voila! Our formula! No algebra required.

The real value of this derivation comes in the from thinking about the data structure that would be traversed by this triplely-nested for loop: an array of dimension NxNxN where elements with an index greater than the row and/or column and/or "depth" do not exist.

Okay, </math nerd blog>.