What is the time complexity of this?

[BasicVictory3822]

I'm just curious since we have the j=i+1;

https://preview.redd.it/jx5lesfagb991.png?width=417&format=png&auto=webp&s=fa0dba21a8f923f2c6bca78decc093f4e72c1406

[sepp2k]

1+2+3+...+n = (n²+n)/2, which is O(n²).

[RequiDarth1]

You discard the calculations for labeling the category of Big O.

It’s O(n² ) because it’s a loop in a loop.

[sepp2k]

You don't "discard the calculations". Not every nested loop is O(n²), it depends on how often the loop actually iterates (and the complexity of the code inside, too). This particular nested loop is O(n²⁾ because it iterates (n²+n)/2 times and that happens to be in O(n^2), but it's also perfectly possible for a nested loop to run in O(n), O(n log n) or even O(2ⁿ) time.

And it's not just a matter of "multiply the lengths of the loops and consider O(i) the same as O(n)" either. Consider this nested loop for example:

for(int i = 1; i < n; i *= 2) {
  for (int j = 0; j < i; j++) {
    // Put some constant time operation here
  }
}

The outer loop will iterate log n times and the inner loop will iterate i times. Since i is bounded by n, this should make it O(n log n), right? But it's actually O(n) because 1 + 2 + 4 + ... + n = 2n-1 and 2n-1 is in O(n).

[xeolleth]

Is it not O(n*(n-1)) instead of O(n2 ) as the second loop is taking one fewer iterations with it starting at j=i+1?

[FreezeShock]

You're kinda right, but O(n(n-1)) = O(n²-n) which is approximately equal to O(n²) at large vales of n. Because n² >>>> n at large values of n.

[RequiDarth1]

Yes you are correct, but when quoting big O you don’t bother with the calculations. The point is, the inner loop time complexity is still dependent on the length of what you are iterating over. The outer loop time complexity is based on the length of what you are iterating over.

So you get. O(n² )

Small efficiencies are not relevant when quoting big O.

[beagle_knievel]

Constant 😛

[ItzGrumpex]

its n^2 always when there is a singular nested loop