I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array   
For i = 0; i < n; i++:
        For j = 0; j < i; j++:

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?


We can write the for loop as the sums;

$$\sum_{i=1}^{n} \sum_{j = 1}^{i} 1 = \sum_{i=1}^{n}i = \frac{n(n+1)}{2} \in\mathcal{O}(n^2) \, .$$

Note: set the starting values from $i = 1$ and $j = 1$, and increment the upper boundaries also. The calculation in the inner function is assumed as a constant operation and it will not change the calculation.


Well that all depends how you want to do it and how comfortable are you with the different ways. You could either make a tree and calculate the leave nodes for the time order. Or you could use the mathematical way as mentioned by others in the answer section. For example if you have a loop like-

{ for(j=1;j<n;j=j*2)

the you would understand that the outer loop works from 1 to n and the inner loop would work from 1 to n also however the step in the inner loop is not a single increment but with every iteration it is becoming double of the previous value hence would execute for logn time. Thereby the net complexity would become O(n*logn).

Hope this helps, I would be more than happy to help you further.


You need to focus on how many times the instructions on the innermost loop will get executed. The outer loops are more like counters.

The inner-loop count will be as follows:

$i = 0; j = \emptyset$
$i = 1; j = 0$
$i = 2; j = 0, 1$
$i = 3; j = 0, 1, 2$

So you have a recurring sum of 1 for $j$ from $0$ to $i-1$, which can be mathematically expressed as:

$$\sum^n_{i = 1}\sum^{i-1}_{j = 0} 1 = \sum^n_{i = 1} i = \frac{n(n + 1)}{2}$$
which is still $O(n^2)$.


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