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.

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|improve this question
add comment

2 Answers

up vote 3 down vote accepted

You need to solve simple formula

$\sum_{i=1}^N\sum_{j=1}^i\sum_{k=i}^j1$

this will give you overall result of

$\frac{1}{6}N(N+1)(N+2)$

Math is easy to do here but I used Wolfram Alpha

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.