[Solved]: Deriving the exact number of execution times

Problem Detail: 

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.

Asked By : Connor Black

Answered By : Realz Slaw

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14843

3.2K people like this

 Download Related Notes/Documents