Algorithmics - The Computing Universe: A Journey through a Revolution - page 97

we looked at two different algorithms - bubble sort and merge sort - and we
claimed that merge sort was much more efficient than bubble sort. How can
we justify such a statement? This type of question is the business of complexity
theory, which examines the computational resources required by an algorithm
or class of algorithms. Typically these resources are measured as time (the num-
ber of computational steps required to solve the problem) or space (how much
memory does it take to solve the problem). Let us look at the time complexity
of our sorting algorithms.
How many operations do we require to sort N objects according to both
algorithms? In the bubble sort algorithm, we have to go through the entire
list of N objects and perform (N - 1) comparisons. We then have to repeat this
process (N - 1) times. To sort a list of length N, we see that for the bubble sort
algorithm, the number of comparisons we are required to carry out is:

Fig. 5.16. In 2009, Robert Bosch from
Oberlin College generated a set of
100,000 points and then ran the TSP
algorithm on this set in order to calcu-
late the minimal path. As the algorithm
proceeds it connects the dots with lines
and the outcome resembles Leonardo
da Vinci's enigmatic painting of the
Mona Lisa.

(N - 1) × (N - 1) = N 2 - 2N +1

Of course there are other statements in the program besides these compari-
sons, but we are only interested in the behavior of the algorithm for large N.
In this case, it is safe for us just to look at the comparisons because the other
parts of the program - involving testing and manipulating indices, for exam-
ple - just take a fixed amount of time. In addition, because for large N, the N 2
term is much larger than the (-2N + 1) term, we can say that the amount of
computational work in the bubble sort algorithm applied to N objects grows
approximately like N 2 . Complexity theorists write this behavior as O (N 2 ), where
the “big- O notation” specifies how the running time of the bubble sort algo-
rithm grows with N.
What about the time complexity behavior of the merge sort algorithm? In
this case we used a divide-and-conquer approach and we do not have to cycle
through the entire list multiple times. For merge sort, we divide the list up
by repeatedly dividing N by 2 and then make comparisons on just the mul-
tiple lists containing 2 items. How many times can we divide a list of length
N? In our example, we started with 8 items and went from 8 to 4 to 2 so there
were three layers and two calls to subroutine Divide. Note that 8 = 2 3 and we
can write the number of layers in terms of logarithms to the base 2. With our
more familiar base 10 logarithms, we can write the power of 10 in 1000 as the
logarithm log 10 1000 = 3. Similarly, we can write the numbers of divisions by 2
for 8 items as the logarithm to base 2, namely log 2 8 = 3 (very handy for binary
machines like computers). In general, for N elements we can write the number
of divisions as log 2 N.
Because the number of divisions grows like log 2 N and the number of com-
parisons we need to make grows like N, the complexity of the merge sort algo-
rithm is O (N log 2 N). This is the beauty of the divide-and-conquer approach.
Table 5.3 shows how the growth rates of N 2 and N log 2 N compare. We see that
N log 2 N grows much more slowly with N than does N 2 - thus showing the
importance of a good sorting algorithm. Any algorithm whose time complexity
grows slower than some polynomial - in this case N log 2 N grows slower than
N 2 - is said to be reasonable . Any problem for which we can find a low-order poly-
nomial time algorithm is said to be tractable , meaning that it can be evaluated
by a computer in an acceptable amount of time.