Programming and Problem Solving with Java

(^558) | Array-Based Lists
N Log 2 N
21
42
83
16 4
32 5
1024 10
32,768 15
1,048,576 20
33,554,432 25
1,073,741,824 30
As you can see, for a list of more than 1 billion values, the binary search algorithm takes only
30 iterations. It is definitely the best choice for searching large lists. Algorithms such as the
binary search algorithm are said to be of logarithmic order.
Now let’s turn to sorting. The methodselectSortcontains nestedforloops. The total number
of iterations is the product of the iterations performed by the two loops. The outer loop executes
N1 times. The inner loop also starts out executingN1 times, but steadily decreases until it
performs just one iteration: The inner loop executesN/2 iterations. The total number of iterations
is thus
Ignoring the constant factor and lower-order term, this is N^2 iterations, and selectSortis an
O(N^2 ) algorithm. Whereas isThere, when coded using the binary search algorithm, takes only 30
iterations to search a sorted array of 1 billion values, putting the array into order takes
selectSortapproximately 1 billion times 1 billion iterations!
Our insertalgorithm for a sorted list forms the basis for an insertion sort,in which values are
inserted into a sorted list as they are input. On average,insertmust shift down half of the val-
ues (N/2) in the list; thus, it is an O(N) algorithm. If we call insertfor each input value, we
execute an O(N) algorithm Ntimes; therefore, an insertion sort is an O(N^2 ) algorithm.
Is every sorting algorithm O(N^2 )? Most of the simpler ones are, but O(Nlog 2 N) sorting algo-
rithms exist. Algorithms that are O(Nlog 2 N) are much closer in performance to O(N)
algorithms than are O(N^2 ) algorithms. For example, if Nis 1 million, then an O(N^2 ) algorithm
takes 1 million times 1 million (1 trillion) iterations, but an O(Nlog 2 N) algorithm takes only 20
million iterations—that is, it is 20 times slower than the O(N) algorithm but 50,000 times faster
than the O(N^2 ) algorithm.
(N – 1) N
2