'Nested for loop in Big Oh Complexity

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

algorithmfor-loopdata-structurestime-complexitybig-o


Solution 1:[1]

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)

Solution 2:[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.

Solution 3:[3]

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

  1. https://stackoverflow.com/a/71805214/17112163
  2. https://stackoverflow.com/a/71537431/17112163
  3. https://stackoverflow.com/a/71146522/17112163
  4. https://stackoverflow.com/a/72046825/17112163
  5. https://stackoverflow.com/a/69821878/17112163

Solution 4:[4]

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)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Tanmay Patil
Solution 2 gnasher729
Solution 3 Deepthi Tabitha Bennet
Solution 4 SabaRish

Related Questions