# Analyzing programs with multiple for-loops

If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...

the ones like

for(i = 1 to n);
for(j = i to n);
x++;


I can use $1 \leq i \leq j \leq n$ and use $x_1 + x_2 + x_3 = n-1$ and find out the general solution which is $\frac{n(n+1)}{2}$. But disconnected loops I have no idea. Consider the following for loops.

    for(i = 1 to n);
for(j = i to n);
for(k = 1 to i*n);
x++; (constant time)

for(i = 1 to n-1);
for(j = i+1 to n);
for(k = 1 to j);
x++; (constant time)


I need to find the general solution.

• Try to trace out the loops for small values of $n$. That might help you understand what's going on, and how to handle "disconnected loops". – Yuval Filmus Feb 4 '13 at 3:21
• I've tried testing these loops with finite values of n, and printed values for different loops, but I couldn't find the pattern... I won't really ask unless I tried for hours... – LarsChung Feb 4 '13 at 4:04
• try to express it as a sum; each iteration contributes 1 to the sum, so youre fine if you just count the number of iterations. how often do the loops execute? – G. Bach Feb 4 '13 at 4:56
• Because the initial value of each loop changes according to the outer loop, I don't think expressing as sum works... if it does can u show me an example? – LarsChung Feb 4 '13 at 5:06
• If the loops are disconnected you can analyze every loop on its own and then sum up the costs. – A.Schulz Feb 4 '13 at 7:56

From your comments, it seems that you are incorrectly calculating the number of loops. And since I do not where to start from for you, I will start from a basic level - please ignore whatever you know or find obvious. I am also going to assume that the semi-colons after each for loop are not present - otherwise in many programming languages, the variable x will be incremented only twice, once after each apparently nested loops.

Counting how many times each loop executes can be written as a discrete summation. For example, a simple for loop from $1$ to $n$, where $1$ operation takes place, can be seen as $\sum\limits_{i = 1}^{n}1 = n$. That is, the loop will execute $n$ times (or the increment statement will be executed $n$ times). Nested loops can be counted as nested summations. When evaluating any summation, consider the iterating variable as the variable, and treat everything else as a constant.

Consider the first set of nested loops. The number of executions/number of times x is incremented can be written as: $$T_1(n) = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1$$ Notice the upper and lower limits on each summation, and compare with your loop variables and ranges. We start evaluation from the innermost loop as follows: \begin{align*} T_1(n) & = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1 = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}in \\ &= \sum\limits_{i = 1}^{n}\left(in \sum\limits_{j = i}^{n}1\right) \ \ \ \ \ \ \text{(considering j as the only variable)} \\ &= \sum\limits_{i = 1}^{n} \left(in(n - i + 1) \right) = \sum\limits_{i = 1}^{n}((n^2 + n)i - ni^2) \\ &= \sum\limits_{i = 1}^{n}\left((n^2 + n)i\right) - \sum\limits_{i = 1}^{n}\left(ni^2\right) \\ &= (n^2 + n)\sum\limits_{i = 1}^{n}i - n\sum\limits_{i = 1}^{n}i^2 \\ &= n(n+1)\cdot \frac{n(n+1)}{2} - n \cdot \frac{n(n+1)(2n+1)}{6} \\ &= \frac{n^2(n+1)(n+2)}{6} \end{align*}

You can verify that if x is initially 0, this will be its value after the first set of nested loops. For the second set, I will provide the the summation and answer, leaving the actual work up to you.

$$T_2(n) = \sum\limits_{i = 1}^{n-1}\sum\limits_{j = i+1}^{n}\sum\limits_{k = 1}^{j}1 = \frac{n(n-1)(n+1)}{3}$$

As others have pointed out, since the two blocks of nested loops are serial, you can just add the number of times each has executed to get the final count as $T(n) = T_1(n) + T_2(n)$. This will give you the number of times x has been incremented. This simple mechanical process should help you out in most instances of nested loops.

• Thx, I found it by asking the TA after I handed in homework.. QQ.. but the way you do it is the same as the TA told me. Also it is possible to use the technique I used to find the general solution, but it's a bit more complicated, so the straight forward way (using series) is alot more convienent! – LarsChung Feb 28 '13 at 9:04

Hint: Consider the following program:

int x = 0;
x += 15;
x += 20;


In the end, $x = 15 + 20 = 35$. A similar idea works for disconnected loops.

• So I tried for the first loop. So I get (n(n+1))/2 for the second loop and (n(n(n+1)))/2 for the second loop. However, if i add them up it doesn't work out... – LarsChung Feb 4 '13 at 4:58
• * third loop for (n(n(n+1)))/2 – LarsChung Feb 4 '13 at 5:07
• @user1926399 Whatever you mean by "work out"... – Raphael Feb 4 '13 at 12:22
• It means the number created by the for loops (through simple program) and the general equation created by ur method are not equal; hence, it's incorrect. – LarsChung Sep 21 '13 at 10:45