Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

marked as duplicate by bartek, Merbs, A.Schulz, sdcvvc, Realz Slaw Dec 10 '12 at 15:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
Paresh, Thanks a lot. This is exactly the sort of explanation I was looking for. I really appreciate it. –  user1779901 Dec 9 '12 at 17:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.