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);

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.

  • 2
    $\begingroup$ 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". $\endgroup$ – Yuval Filmus Feb 4 '13 at 3:21
  • $\begingroup$ 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... $\endgroup$ – LarsChung Feb 4 '13 at 4:04
  • $\begingroup$ 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? $\endgroup$ – G. Bach Feb 4 '13 at 4:56
  • $\begingroup$ 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? $\endgroup$ – LarsChung Feb 4 '13 at 5:06
  • $\begingroup$ If the loops are disconnected you can analyze every loop on its own and then sum up the costs. $\endgroup$ – 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.

  • $\begingroup$ 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! $\endgroup$ – 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.

  • $\begingroup$ 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... $\endgroup$ – LarsChung Feb 4 '13 at 4:58
  • $\begingroup$ * third loop for (n(n(n+1)))/2 $\endgroup$ – LarsChung Feb 4 '13 at 5:07
  • $\begingroup$ @user1926399 Whatever you mean by "work out"... $\endgroup$ – Raphael Feb 4 '13 at 12:22
  • $\begingroup$ 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. $\endgroup$ – LarsChung Sep 21 '13 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.