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

-
I think there's a straightforward way to improve your 30 percent accept rate. –  Gerry Myerson Jan 16 '13 at 11:10
Bob John - It seems, from your accept rate, that you haven't found answers very helpful. Users are likely to be discouraged from answering, since they may think they won't help. If you do find answers to be helpful, you can (1) upvote them. (Click on the greyed-out "upwards" arrows above the answers' vote count.) (2) You can accept one answer per question: to do this, click on the "greyed-out" check-mark to the left of the answer you want to accept. –  amWhy Jan 19 '13 at 14:41

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