Java™ How To Program (Early Objects), Tenth Edition

19.3.3 O(n²) Algorithms

Now suppose you have an algorithm that tests whether any element of an array is duplicated elsewhere in the array. The first element must be compared with every other element in the array. The second element must be compared with every other element except the first (it was already compared to the first). The third element must be compared with every other element except the first two. In the end, this algorithm will end up making (n – 1) + (n – 2) + ... + 2 + 1 or n²/2 – n/2 comparisons. As n increases, the n² term dominates and the n term becomes inconsequential. Again, Big O notation highlights the n² term, leaving n/2. But, as we’ll soon see, constant factors are omitted in Big O notation.

Big O is concerned with ...