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

  • 0
    @MartinSleziak Thanks Martin!!2012-11-29

4 Answers 4

4

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}

  • 0
    @copper.hat Thank you very much!! this is the best I've got by far..2012-11-29
2

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*}$

  • 0
    I wanted the no of times of execution of that statement.. but thanks anyways Dennis2012-11-29
2

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*}

1

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
  • each tuple $(j,j,i)$ with $1 \le j
  • each tuple $(j,i,i)$ with $1 \le j
  • 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}$.

  • 0
    added a simpler way to get the result2012-12-02