Triple nested for-loops [duplicate]

Question

Possible Duplicate:
A puzzle related to nested loops

I am trying to count the exact/total number of iterations the following nested for-loops are executed:

s=0
for (i: 1 to n)
 for (j: 1 to i)
  for (k: j to i)
   s = s + 1

I know that the first two for-loops will have n(n+1)/2 iterations. My problem is with the third for-loop. Due to this third loop what factor am I supposed to multiply with n(n+1)/2 to get the total number of iterations?

Any help would be appreciated? Thanks

Answer 1

Instead of a general "formula", you should try to work out from principles first, at least in the beginning. You can see that the number of executions are:

$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1$$

We try solving them one step at a time. The innermost (right-most) summation can be solved as:

$$\sum\limits_{k=j}^{i} 1 = i - j + 1$$ (how many times will the loop execute from $j$ to $i$, inclusive).

Going on to the next level, by substituting the above result, we get: $$\sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1 = \sum\limits_{j=1}^{i} (i - j + 1) = i\sum\limits_{j=1}^{i} 1 -\sum\limits_{j=1}^{i}j + \sum\limits_{j=1}^{i}1$$ $$ = i^2 - \frac{i(i+1)}{2} + i = \frac{i(i+1)}{2}$$

Notice that when summation is over the variable $j$, $i$ behaves like a constant, and so could be taken out of the summation.

The above expression gives the number of times the inner two loops are executed for every value $i$ that the outer loop takes. Solving the outermost summation with this expression ($i$ runs from $1$ to $n$), we have:

$$\sum\limits_{i=1}^{n}\frac{i(i+1)}{2} = \frac{1}{2}\sum\limits_{i=1}^{n}i^2 + \frac{1}{2}\sum\limits_{i=1}^{n}i$$ $$ = \frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6} + \frac{1}{2}\cdot\frac{n(n+1)}{2}$$ $$ = \frac{n(n+1)(n+2)}{6}$$

This will also be the value of the variable s in your pseudocode. I suggest that you should approach these kind of questions from the basics, and revise the summation rules. There are no general formulas or multiplication factors for some arbitrary nesting of loops. You might even want to go along these lines to again derive your result for the first two loops only.