Is looping an array to compare to itself considered O(n^2)? [duplicate]

Question

This question already has answers here:

What is O(…) and how do I calculate it? (2 answers)

Closed 7 months ago.

Often when I'm doing an operation comparing an array to itself, I write code along these lines:

function operation (array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      // do something with array, i, and j
    }
  }
}

While the runtime of this code (starting j at i + 1) is clearly faster than a normal double-nested loop, I'm struggling to figure out if that's just a matter of a smaller coefficient or if it should be represented by a different big O.

Is there a better big O for the above function than n squared?

Answer 1

It's still O(n^2), with a constant coefficient of 1/2.

The number of times the inner loop is executed is (i-1) + (i-2) + (i-3) ... + 3 + 2 + 1 with the total number of terms being i. Note that the first and last term add up to i, as do the second and second-to-last, etc. So there are i/2 pairs, each of which adds up to i - which makes a total of i/2 * i = 1/2 * i^2

This is actually the idea famously used by an elementary school aged Carl Friedrich Gauss circa 1785 to outwit his teacher on a make-work assignment.

Answer 2

Of course, if you know that the data is sorted, you would most certainly use a more intelligent algorithm, such as "binary search."

If you "brute-force loop through the array, without any consideration of its known properties," then of course you richly deserve your fate.