Time complexity of nested for loop

Question

Hi,

I need to calculate the time complexity of the following code:

for(i=1; i<=n; i++)
{
 for(j=1; j<=i; j++)
 {
   // Some code
 }
}

Is it O(n^2)?

Answer 1

Indeed, it is O(n^2). See also a very similar example with the same runtime here.

Answer 2

Yes, one way quick way to get a big O notation is to look at nested for loops.

Typically (but not always) one loop nested in another will cause O(n^2).

Think about it, the inner loop is executed i times, for each value of i. The outer loop is executed n times.

thus you see a pattern of execution like this: 1 + 2 + 3 + 4 + ... + n times

Therefore, we can bound the number of code executions by saying it obviously executes more than n times (lower bound), but in terms of n how many times are we executing the code?

Well, mathematically we can say that it will execute no more than n^2 times, giving us a worst case scenario and therefore our Big-Oh bound of O(n^2). (For more information on how we can mathematically say this look at the Power Series)

Big-Oh doesn't always measure exactly how much work is being done, but usually gives a reliable approximation of worst case scenario.

Answer 3

OK, thanks.