Time complexity of nested for-loop

160,151

Solution 1

Yes, nested loops are one way to quickly get a big O notation.

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

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² times, giving us a worst case scenario and therefore our Big-Oh bound of O(n²). (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.

4 yrs later Edit: Because this post seems to get a fair amount of traffic. I want to more fully explain how we bound the execution to O(n²) using the power series

From the website: 1+2+3+4...+n = (n² + n)/2 = n²/2 + n/2. How, then are we turning this into O(n²)? What we're (basically) saying is that n² >= n²/2 + n/2. Is this true? Let's do some simple algebra.

Multiply both sides by 2 to get: 2n² >= n² + n?
Expand 2n² to get:n² + n² >= n² + n?
Subtract n² from both sides to get: n² >= n?

It should be clear that n² >= n (not strictly greater than, because of the case where n=0 or 1), assuming that n is always an integer.

Actual Big O complexity is slightly different than what I just said, but this is the gist of it. In actuality, Big O complexity asks if there is a constant we can apply to one function such that it's larger than the other, for sufficiently large input (See the wikipedia page)

Solution 2

A quick way to explain this is to visualize it.

if both i and j are from 0 to N, it's easy to see O(N^2)

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

in this case, it's:

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

This comes out to be 1/2 of N^2, which is still O(N^2)

Solution 3

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

Solution 4

Let us trace the number of times each loop executes in each iteration.

for (int i = 1; i <= n; i++){  // outer loop
    for (int j = 1; j <= i; j++){  // inner loop
        // some code
    }
}

In the first iteration of the outer loop (i = 1), the inner loop executes once.

In the second iteration of the outer loop (i = 2), the inner loop executes twice.

In the third iteration of the outer loop (i = 3), the inner loop executes thrice.

So, in the last iteration of the outer loop (i = n), the inner loop executes n times.

Therefore, the total number of times this code executes is

1 + 2 + 3 + … + n

= (n(n + 1) / 2) (Sum of Natural Numbers Formula)

= (((n^2) + n) / 2)

= O(n^2)

——————

Also, do take a look at these

Solution 5

On the 1st iteration of the outer loop (i = 1), the inner loop will iterate 1 times On the 2nd iteration of the outer loop (i = 2), the inner loop will iterate 2 time On the 3rd iteration of the outer loop (i = 3), the inner loop will iterate 3 times
.
.
On the FINAL iteration of the outer loop (i = n), the inner loop will iterate n times

So, the total number of times the statements in the inner loop will be executed will be equal to the sum of the integers from 1 to n, which is:

((n)*n) / 2 = (n^2)/2 = O(n^2) times

View more solutions

160,151

Author by

yyy

Updated on July 08, 2022

Comments

yyy almost 2 years
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)?
erstaples about 9 years

Thanks for finally helping me understand how inner loops with a j<=i condition result in 1/2 N^2. This has been bothering me for some time. Can you explain how this is still O(N^2)?
Krys Jurgowski about 9 years

Due to Moore's law, we can assume that the speed of algorithm execution doubles about every 18 months. Because of this, when analyzing algorithms, we can drop the coefficient and just focus on algorithms in terms of n. Basically O(n^2) will take O(1/2 n^2) in 18 months. As n grows higher though, runtime grows exponentially, where for a linear time algorithm, it grows with n.
erstaples about 9 years

So, what you're saying is that when calculating big Oh notation, the 1/2 in 1/2(n^2) is unimportant, due in part to the fact that coefficients become irrelevant over time? The important part of that term - again, in terms of big Oh - is that it's quadratic, not that it is a quadratic that gets halved?
Krys Jurgowski about 9 years

Yes exactly. Also that the runtime grows exponentially. When your data goes from 100 points to 10,000 to 10,000,000, your algorithm becomes unusable because the runtime can't scale with the input. cl.cam.ac.uk/~djg11/speedo/run1-plot.png
TSL_ about 8 years

May I ask a small question here? what if the "//some code" part is some computation with O(N) complexity, how is the result calculated? I think this is the common case where one function calls another and considers the later as a black-box having some complexity provided by specs?
AndyG about 8 years

@ShawnLe: Insightful observation. In most assumptions, yes, we assume that //some code is O(1), and therefore does not get factored into Big O complexity. If it were in fact O(N), then our overall complexity becomes O(N^3). Think of it as multiplication (because it is). For ~N outer loop iterations, the inner loop iterates ~N times, with each iteration performing ~N work. N times N times N = N^3.
eaglei22 over 5 years

Can you write the proof to N*M = N^2? To help understand it better.
Duxa about 5 years

Dont forget heapifying a heap is two nested loops (as you build the heap), but its O(n).
Robin Andrews over 2 years

I would be curious to know why we can make this simplification.
nate sire almost 2 years

This seems like the correct answer. The other answers assume both loops have the same n?