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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a given input $N$, how many times does the enclosed statement executes?

for $i$ in $1\ldots N$ loop
$\quad$for $j$ in $1\ldots i$ loop
$\quad$$\quad$for $k$ in $i\ldots j$ loop
$\quad$$\quad$$\quad$$sum = sum + i$ ;
$\quad$$\quad$end loop;
$\quad$end loop;
end loop;

Can anyone figure out an easy way or a formula to do this in general. Please explain.

share|cite|improve this question
up vote 4 down vote accepted

You need to solve simple formula


this will give you overall result of


Math is easy to do here but I used Wolfram Alpha

share|cite|improve this answer

What you really count in the variable $\text{sum}$ are triples of the form $$\{ (a,b,c) \mid 1\le a<b<c\le N\}.$$

Clearly there are $N(N-1)(N-2)$ triples of different elements. Since you only consider sorted triples, you only count one of the possible $6=3!$ permutations for every triple containing $a,b,c$. Therefore you overcount by a factor of $6$, and this gives you $\text{sum}=N(N-1)(N-2)/6$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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