问题描述:

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:

您可能感兴趣的文章：

- How to add an xml file to erlang edoc documentation
- sql - How can I select two fields from two different tables in a Django join?
- PHPExcel : Reading cell values with rangetoArray() function and apply sum formula
- java - Cannot resolve symbol 'Immutable'
- send request to a servlet from JSP on loading the JSP without user input(like button)
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**