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)*?

Asked 7 Months ago Answers: 2 Viewed 41 times

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)*?

85

The `if`

condition will be true when `j`

is a multiple of `i`

; this happens `i`

times as `j`

goes from 0 to `i * i`

, so the third `for`

loop runs only `i`

times. The overall complexity is O(n^4).

```
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i*i; j++) // Runs O(n) times
{
if (j % i == 0) // Runs O(n) × O(n^2) = O(n^3) times
{
for (int k = 0; k < j; k++) // Runs O(n) × O(n) = O(n^2) times
{
sum++; // Runs O(n^2) × O(n^2) = O(n^4) times
}
}
}
}
```

Friday, August 27, 2021

answered 4 Months ago

Only authorized users can answer the question. Please sign in first, or register a free account.

Not the answer you're looking for? Browse other questions tagged :

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 seriesFrom 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.

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)