# How many times will “statement” be executed?

Suppose we have the following:

for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
//statement

for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
for(int k = j; k <= n; ++k)
//statement


In either case, is there a straightforward way to know how many times "statement" will be executed? Thank you.

-

Yes. You are effectively computing

$$\sum_{i=1}^n \sum_{j=i}^n 1 = \sum_{i=1}^n (n-i+1) = n(n+1) - \sum_{i=1}^n i = \frac{n(n+1)}{2}.$$

In this case there's an easy geometric way of visualizing the sum: you're counting the number of entries in a $n\times n$ matrix lying on or below the diagonal.

Similarly

\begin{align*} \sum_{i=1}^n \sum_{j=i}^n \sum_{k=j}^n &= \sum_{i=1}^n \sum_{j=i}^n (n-j+1)\\ &= \sum_{i=1}^n\left[\sum_{j=i}^n(n+1) - \sum_{j=i}^nj\right]\\ &= \sum_{i=1}^n\left[(n-i+1)(n+1) - \sum_{j=i}^nj\right]\\ &= \sum_{i=1}^n\left[(n-i+1)(n+1) - \left(\sum_{j=1}^n j-\sum_{j=1}^{i-1}j\right)\right]\\ &=\sum_{i=1}^n\left[(n-i+1)(n+1) - \frac{n(n+1)}{2} + \frac{i(i-1)}{2}\right]\\ &= n(n+1)^2 - \frac{n^2(n+1)}{2} - \frac{n(n+1)^2}{2} - \frac{n(n+1)}{4} + \frac{n(n+1)(2n+1)}{12}\\ &=\frac{n(n^2+3n+2)}{6}. \end{align*}

-
Can you elaborate on the steps in the triple summation? Namely, how we arrive at this: $= \sum_{i=1}^n\left[(n-i+1)(n+1) - \sum_{j=i}^nj\right]\\$ and this: $=\sum_{i=1}^n\left[(n-i+1)(n+1) - \frac{n(n+1)}{2} + \frac{i(i-1)}{2}\right]\\$ –  Bob John Jan 16 '13 at 7:18
I've added some extra steps. –  user7530 Jan 16 '13 at 7:38

more short answer would be C(n+2,3) + C(n+1,2) by fundamental principles of counting C(n+the number of loop-1,the number of loop)

-