How to properly calculate dependent nested loops for big-O [duplicate]

Question

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?

Answer 1

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.

Answer 2

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(i=1;i<n;i++)
{ for(j=1;j<n;j=j*2)
  {anyfunc();
}}

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.

Answer 3

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$
$\dots$

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