# Deriving the exact number of execution times

So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions.

Here's a screen cap:

The answer is n^2(n+1)/2.

I would appreciate a very simple walk through and/or a pointer to some good material.

Hint: Summation. Also note you can optionally reorder the (non-dependent) loops.

Spoiler (mouse over):

So what you normally do: the inside of a nested loop will run the $\text{number of loops of the outer loop} \times \text{the number of loops of the inner loop}$. It can also be done with repeated addition of the number of loops of the inner loop (after all multiplication can be done with repeated addition). In this case, one of the inner loops is dependent on the outer loop, so you can't just multiply them. You must add it more "manually". If you do this, you will see something like this: $1 + 2 + 3 ... n$, this can be done with summation, which in this case $\sum_{i=1}^n i = \frac {n\cdot\left(n+1\right)} {2}$. And multiplying the additional $\#n$-loop loop (you can reorder $k$-loop to the outside to make this simpler, after that you can calculate the two inner-loops, $i$ and $j$) , you get $n\cdot\frac {n\cdot\left(n+1\right)} {2} =\frac {n^2\cdot\left(n+1\right)}{2}$.

So step by step:

1. First let's decide the two outer loops: the outer loop, $i$ will run $n$ times.
2. The $j$ loop will run $1...i$ each time. The first time it will run $1$ time, then $2$ times, then $3$ ... finally $n$ times, totaling $1 + 2 + 3 + ... + n$ times. That means the $j$ loop will run a total of $\frac{n\cdot\left(n+1\right)}{2}$ times, after calculating the summation (see linked wikipedia page on summation).
3. For each time the $j$ loop runs, the $k$ loop will run $n$ times, thus we simply multiply the summation result by $n$ for $\frac{n^2\cdot\left(n+1\right)}{2}$.

Work it out from the inside out.

Let $P'''(i, j, k) =$ cout << i << j << k << endl and $T'''(i,j,k)$ be the number of times cout << … is executed during the execution of $P'''(i,j,k)$ when i$=i$, j$=j$ and k$=k$. As it happens, $T'''(i,j,k)$ does not depend on the value of any of the variables: $T'''(i,j,k) = 1$.

Let $P''(i,j) =$ for k = 1 to n $P'''(i,j,\mathtt{k})$ and $T''(i,j)$ be the number of times cout << … is executed during the execution of $P''(i,j)$ when i$=i$ and j$=j$. The number of times the instruction is executed during the execution of the loop is the sum of the number of times it is executed during each iteration. \begin{align} T''(i,j) &= \sum_{k=1}^n T'''(i,j,k) = T'''(i,j,1) + T'''(i,j,2) + \ldots + T'''(i,j,n) \\ &= \sum_{k=1}^n 1 = n \end{align}

Let $P'(i) =$ for j = 1 to i $P_(i,\mathtt{j})$ and define $T'(i)$ like before. \begin{align} T'(i) &= \sum_{j=1}^i T''(i,j) = \sum_{j=1}^i n = i \cdot n \end{align}

Let $P =$ for i = 1 to n $P'(\mathtt{i})$ and define $T$ like before. $T$ is the number you're looking for. \begin{align} T &= \sum_{i=1}^n T'(i) = \sum_{i=1}^n (i \cdot n) = n \sum_{i=1}^n i = n \cdot \frac{n (n+1)}{2} \end{align}