# algorithm - What's the Big-Oh for nested loops i=0..n-2, j=i+1..n-1?

Given the following code:

``for (int i = 0; i < n-1; ++i){for (int j = i+1; j < n; ++j){// Do work.}}``

What is the Big-Oh value for it (over `n`)? I'm thinking it's O(N^2) but I'm not sure.

I did find a similar question here: complexity for nested loops

but it's not quite the same I think.

Yes, that's `O(N^2)`. Pair up the iterations of the inner loop in the beginning and at the end of the outer loop, like this:

The inner loop will execute...

• `N-1` times on the first iteration of the outer loop, and `1` time on the last iteration
• `N-2` times on the second iteration of the outer loop, and `2` times on the second to last iteration
• `N-3` times on the third iteration of the outer loop, and `3` times on the third to last iteration
• ... and so on; you will have `N/2` pairs like that; when `N` is odd, the last pair is incomplete.

You can see that each of the pairs executes a total of `N` times, and you have `N/2` such pairs, for a total of `N*(N-1)/2` times.

The way the formula is derived comes from the derivation of the formula for the sum of arithmetic progression with the common difference of `1`.

It should be possible to check it this way.

``````int z = 0, n = 10; // try 20 etc
for (int i = 0; i < n-1; ++i)
{
for (int j = i+1; j < n; ++j)
{
z++;
}
}
``````

Now, check the value of z.

``````With n = 10; z becomes 45
With n = 20; z becomes 190
With n = 40; z becomes 780
``````

A doubling in n caused z to become ~4 times its value. Hence, it is approximately `O(n^2)`.

Methodically, using Sigma notation (empirically verified), you can obtain the exact number of iterations plus the order of growth complexity: