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

19.3.2 O(n) Algorithms

An algorithm that tests whether the first array element is equal to any of the other array elements will require at most n – 1 comparisons, where n is the number of array elements. If the array has 10 elements, this algorithm requires up to nine comparisons. If the array has 1000 elements, it requires up to 999 comparisons. As n grows larger, the n part of the expression “dominates,” and subtracting one becomes inconsequential. Big O is designed to highlight these dominant terms and ignore terms that become unimportant as n grows. For this reason, an algorithm that requires a total of n – 1 comparisons (such as the one we described earlier) is said to be O(n). An O(n) algorithm is referred to as having a linear run time ...