0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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