Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 $j\ldots i$ 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.

share|improve this question
    
Should the 'for k in i..j loop' have the i and j reversed? –  copper.hat Nov 29 '12 at 8:35
    
I've retagged your question since it is definitely not about linear-programming, see the tag-wiki. Of course, if you can find other appropriate tags, feel free to add them or replace the ones I've put to your post. –  Martin Sleziak Nov 29 '12 at 8:52
    
@copper.hat no.. it's just the way it is :) –  VISHNU VIVEK Nov 29 '12 at 11:28
    
@MartinSleziak Thanks Martin!! –  VISHNU VIVEK Nov 29 '12 at 11:28
add comment

4 Answers 4

up vote 4 down vote accepted

The number of times the inside statement is executed is $S = \sum_{i=1}^N \sum_{j=1}^i \sum_{k=i}^j 1$.

\begin{eqnarray} S &=& \sum_{i=1}^N \sum_{j=1}^i (i-j+1) \\ & = & \sum_{i=1}^N (i(i+1)-\frac{1}{2} i(i+1)) \\ & = & \frac{1}{2} \sum_{i=1}^N (i^2 +i) \\ & = & \frac{1}{2} (\frac{1}{6}N(N+1)(2N+1)+ \frac{1}{2}N (N+1)) \\ & = & \frac{1}{6} N(N+1)(N+2) \end{eqnarray}

share|improve this answer
1  
Since he is not adding 1 but i in the innermost cycle, the number of executions is not the same as the sum. –  Martin Sleziak Nov 29 '12 at 8:48
    
That is correct. I am computing the number of times the statement is executed, not the sum? –  copper.hat Nov 29 '12 at 8:49
    
My mistake, I should have read the OP more carefully. (I assumed he wants the sum.) –  Martin Sleziak Nov 29 '12 at 8:50
    
Initially I did too. –  copper.hat Nov 29 '12 at 8:51
    
@copper.hat Thank you very much!! this is the best I've got by far.. –  VISHNU VIVEK Nov 29 '12 at 11:32
add comment

There is also a combinatorical way to find the solutiopn of you question. Check wich values takes the tupel $(j,k,i)$ in the most inner loop? Each tuple $(j,k,i)$ with $1 \le k \le N$ exactly once.

So

  • each tuple $(j,k,i)$ with $1 \le j<k<i \le N$
  • each tuple $(j,j,i)$ with $1 \le j<i \le N$
  • each tuple $(j,i,i)$ with $1 \le j<i \le N$
  • each tuple $(j,j)$ with $1 \le j \le N$

The first number is $\binom{N}{3}$, the second and the third is $\binom{N}{2}$, the fourth is $\binom{N}{1}$. $$(\binom{N}{3} + \binom{N}{2} ) + (\binom{N}{2}+ \binom{N}{1})=\binom{N+1}{3}+\binom{N+1}{2}=\binom{N+2}{3}=\frac{n(n+1)(n+2)}{6}=\binom{n+2}{3}$$

Edit

This result can be proved in a direct way:

Take the $n+2$ element set $M=\{\text{"j=k"},1,...,N,\text{"i=k"}\}$. The set contains of the $N$ numbers $1,...,N$ and the two strings $\text{"j=k"}$ and $\text{"i=k"}$. A three element subset $S$ of $M$ can be of exactly one of the following types:

  1. $S=\{j,k,i\} , 1 \le j \lt k \lt i \le N$
  2. $S=\{\text{"j=k"},k,i\}, 1 \le k \lt i \le N$
  3. $S=\{j,k,\text{"i=k"}\}, 1 \le j \lt k \le N$
  4. $S=\{\text{"j=k"},k,\text{"i=k"}, 1 \le k \le N$

The sets of these four list items correspond to the tuples of the corresponding items of the former list. But this four types of sets contain all the three element subsets of the set M and the number of three element subsets of $M$ is $\binom{n+2}{3}$.

share|improve this answer
    
thank you for the answer!!! –  VISHNU VIVEK Nov 30 '12 at 12:01
    
added a simpler way to get the result –  miracle173 Dec 2 '12 at 7:50
add comment

For any value of $i$, the $j$-loop executes $i$ times. For any value of $j$, the $k$-loop executes $i-j+1$ times, and each time we add $i$ to the sum. Assuming the initial $sum$ was $0$, we have: $$\begin{align*}sum&=\sum_{i=1}^N \sum_{j=1}^i i(i-j+1)=\sum_{i=1}^N \sum_{j=1}^i (i^2+i-ji)=\sum_{i=1}^N \left((i^2+i)i-i\frac{i(i+1)}{2}\right)=\\ &=\frac12\sum_{i=1}^N \left(2i^3+2i^2-i^3-i^2\right)=\frac12\sum_{i=1}^N\left(i^3-i^2\right)=\frac12\left(\frac{N^2(N+1)^2}{4}-\frac{N(N+1)(2N+1)}{6}\right)=\\ &=\frac{1}{24} (N-1) N (N+1) (3 N+2)\end{align*}$$

share|improve this answer
1  
@VISHNU VIVEK: I thought you wanted the sum, but reading your question again, I see that you just wanted the number of times the loop executes. In that case, the other answers are the correct. I left my answer anyway, just in case :) –  Dennis Gulko Nov 29 '12 at 9:02
    
I wanted the no of times of execution of that statement.. but thanks anyways Dennis –  VISHNU VIVEK Nov 29 '12 at 11:34
add comment

So you're asking for the value of $$ S = \sum_{i=1}^N\sum_{j=1}^i(i-j+1). $$ Write $S_i$ for the inner sum. Then $$ S_i = i^2 - \sum_{j=1}^i j + i = i^2 - \frac{i(i+1)}2 + i = \frac12 i^2 + \frac12 i.$$ Then the outer sum is \begin{align*} S &= \frac12\sum_{i=1}^N i^2 + \frac12\sum_{i=1}^n i\\ &= \frac{N(N+1)(2N+1)}{12} + \frac{N(N+1)}4\\ &= \frac{N(N+1)(N+2)}{6}. \end{align*}

share|improve this answer
    
Thank you very much!! –  VISHNU VIVEK Nov 29 '12 at 11:34
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.