[Solved]: Analyzing programs with multiple for-loops

Problem Detail: 

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.

Asked By : LarsChung

Answered By : Paresh

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.

Best Answer from StackOverflow

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