Analysis of Algorithms : An Active Learning Approach

1.5 DIVIDE AND CONQUER ALGORITHMS 29

tions, we need to know the absolute smallest number of operations needed to
solve a particular problem. This must be determined by looking at the prob-
lem itself and not any particular algorithm to solve it. This lower bound tells us
the amount of work that is necessary to solve the problem and shows that any
algorithm that claims to be able to solve the problem more quickly must fail in
some cases.
We can again use a binary tree to help us analyze the process of sorting a list
of three numbers. We can construct a binary tree for the sorting process by
labeling each internal node with the two elements of the list that would be
compared. The ordering of the elements that would be necessary to move
from the root to that leaf would be in the leaves of the tree. The tree for a list
of three elements is shown in Fig. 1.4. Trees of this form are called decision
trees.
Each sort algorithm produces a different decision tree based on the elements
that it compares. Within a decision tree, the longest path from the root to a

x 1 ≤x 2

x 1 ≤x 3 x 1 ≤x 3

x 2 ≤x 3 x 3 ,x 1 ,x 2 x 2 ≤x 3

x 1 ,x 2 ,x 3 x 1 ,x 3 ,x 2

x 2 ,x 1 ,x 3

x 2 ,x 3 ,x 1 x 3 ,x 2 ,x 1

■FIGURE 1.4

The decision tree for

sorting a three-

element list