Half the Work, Same Class

This method checks a single array for duplicate values:

public boolean hasDuplicates(int[] a) {
  for (int i = 0; i < a.length; i++) {
    for (int j = i + 1; j < a.length; j++) {
      if (a[i] == a[j]) {
        return true;
      }
    }
  }

  return false;
}

Take the array to have length $n$. What is the Big-Oh of this method?

The loops are nested again, so you might expect $O(n^2)$. That is the right answer. But the inner loop here does noticeably less work than in the previous example, and I want to walk through why the answer comes out the same anyway.

Look at where the inner loop starts. It starts at j = i + 1, not at j = 0, so it does not scan the whole array each time. We can draw the same grid as before, with a · for a comparison yet to be made, a ░ for one already made, and a █ for the one happening now. When i = 0 the inner loop skips the cell where j = i and visits the rest of the row:

      j=0  j=1  j=2  j=3
i=0   ·    ░    ░    █
i=1   ·    ·    ·    ·
i=2   ·    ·    ·    ·
i=3   ·    ·    ·    ·

The next row starts one cell further along, at j = i + 1 = 2:

      j=0  j=1  j=2  j=3
i=0   ·    ░    ░    ░
i=1   ·    ·    ░    █
i=2   ·    ·    ·    ·
i=3   ·    ·    ·    ·

When i = 0 the inner loop runs $n-1$ times; when i = 1 it runs $n-2$ times; and so on down to $0$ when i = n - 1. Each row covers only the cells to the right of the diagonal, so the visited cells fill the upper triangle and leave the lower triangle empty:

      j=0  j=1  j=2  j=3
i=0   ·    ░    ░    ░
i=1   ·    ·    ░    ░
i=2   ·    ·    ·    ░
i=3   ·    ·    ·    ·

So the total number of inner iterations is

$$(n-1)+(n-2)+\cdots +1+0$$

That sum has a closed form:

$$\frac{n(n-1)}{2}=\frac{1}{2}{n}^2-\frac{1}{2}n$$

It is not hard to derive that formula. Look up the Gauss Summation trick if you want to see it. The total is about half of $n^2$, so the inner loop does half as many iterations as in the previous example. Still, asymptotically, it is $O(n^2)$. We drop the constant factor of one-half, and we drop the lower-order term.