Nested for loop in Big Oh Complexity

Question

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++){
        // do swap stuff, constant time
    }
}

I read that single for loop is O(N) and traversing it twice will make it O(n^2).

I watched related tutorials which shows that each operation takes unit of 1 - O(1). I would like see in details how O(n^2) actually came up. I tried to do math for each statement but I believe I am not doing it right. I would appreciate if someone can literally show me how nested for loop becomes O(n^2). Thanks beforehand

You have N elements each taking 1 operation and for each operation you do N more operations. — Christo S. Christov, Feb 11 '15 at 07:46
The inner loop will run: `1+2+3+4+...+n = n(1+n)/2 => O(n^2)` — Nir Alfasi, Feb 11 '15 at 07:48
@alfasin Could you please be more specific with your answer ? — , Feb 11 '15 at 07:53
Can you please be more specific in your question ? which part didn't you understand? — Nir Alfasi, Feb 11 '15 at 08:03
Possible duplicate of [Time complexity of nested for-loop](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) — Bernhard Barker, Sep 06 '17 at 19:10

score 2 · Answer 1 · answered Feb 11 '15 at 07:56

2

You need to use the ancient and obscure art of mathematics and calculate the number of times that the inner statement is executed.

In your case, the inner loop is executed i times. The values for i are 0, 1, 2, ..., n-1. So you need a formula that calculates this sum, and that's your result.

You read that a single loop is O (n). That's nonsense. It depends on the loop.

for (i = 1; i < n; i *= n)

doesn't iterate n times. It iterates log2 (n) times, which is usually an awful lot less. You need to look at the actual code and figure it out. There is no simple rule for this.

answered Feb 11 '15 at 07:56

gnasher729

51,477
5
75
98

1

`for (i = 1; i < n; i *= n)` Won't this loop run only once? – Anshul Goyal Feb 11 '15 at 08:27
1

I think he/she meant `i *= 2`. – Tanmay Patil Feb 11 '15 at 12:49

score 2 · Answer 2 · answered Apr 28 '22 at 16:05

for(int i = 0; i < n; i++){  // outer loop
    for(int j = 0; j < i; j++){  // inner loop
        //do swap stuff, constant time
    }
}

In the first iteration of the outer loop (i = 0), the inner loop doesn’t execute.

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

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

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

score 1 · Accepted Answer · answered Feb 11 '15 at 08:04

As you mentioned

Each takes unit of 1 - O(1)

So each iteration of the inner loop takes 1, 2, 3, ... , n unit time.

total_time = 1 +   2   +   3   + ... + (n-2) + (n-1) + n

Reversing

total_time = n + (n-1) + (n-2) + ... +   3   +   2   + 1

Adding

2 * total_time = (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)

There are total n terms

2 * total_time = (n+1) * n

=> total_time = (n+1) * n / 2

=> total_time = n^2 / 2 + n / 2

Lower terms and constant coefficients are neglected for big O complexity.

As a result

O(n^2)

score 0 · Answer 4 · answered Feb 11 '15 at 07:53

0

A function that loops from i = 1 to n and then has a inner loop that goes from 1 to i would go though a number of iteration equal to this formula:

n(n+1)/2

As you can see, when we get rid of everything besides the main exponent, you end with O(n^2)

answered Feb 11 '15 at 07:53

SabaRish

105
11

read this also http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – SabaRish Feb 11 '15 at 07:55

Nested for loop in Big Oh Complexity

4 Answers4

Linked