StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You are correct that you're doing fewer than n<sup>2</sup> operations. The question is how many fewer operations you are doing.</p> <p>Let's think about how many pairs there are in the array. If each of the n numbers can be paired with (n - 1) other numbers, the total number of pairs possible is n(n - 1). Each iteration of the original for loop generates one of these pairs, so the total number of pairs you generate is n<sup>2</sup> - n, which is O(n<sup>2</sup>).</p> <p>Now, what about if you eliminate duplicate pairs by saying that (1, 4) and (4, 1) are the same? In this case, note that half of the pairs you generate are going to be extraneous - you'll generate each pair twice. This means that the number of pairs is (n<sup>2</sup> - n) / 2. This expression is less than n<sup>2</sup>, but notice that it is still O(n<sup>2</sup>) because big-O notation ignores constants.</p> <p>In other words - you are right that you are generating fewer than n<sup>2</sup> pairs, but the total number of pairs you're creating is still O(n<sup>2</sup>).</p> <p>More generally - if you ever decrease the total amount of work that an algorithm does by some constant factor (say, you cut the work in half, or cut the work by a factor of 100), you have not changed the big-O runtime of the algorithm. Big-O completely ignores constants. In order to decrease the big-O runtime, you need to decrease the total amount of work by an amount that is more than a constant; say, by a factor of n, log n, etc.</p> <p>Hope this helps!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload