Skip to main content
4 of 4
added 8 characters in body
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

How to properly calculate dependent nested loops for big-O

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?

Confuto
  • 123
  • 1
  • 4