Page 549 - Discrete Mathematics and Its Applications

528 8 / Advanced Counting Techniques

We will first set up the divide-and-conquer recurrence relations that can be used to study
the complexity of some important algorithms. Then we will show how to use these divide-and-
conquer recurrence relations to estimate the complexity of these algorithms.
EXAMPLE 1 Binary Search We introduced a binary search algorithm in Section 3.1. This binary search
algorithm reduces the search for an element in a search sequence of size n to the binary search
for this element in a search sequence of size n/2, when n is even. (Hence, the problem of size n
has been reduced to one problem of size n/2.) Two comparisons are needed to implement this
reduction (one to determine which half of the list to use and the other to determine whether any
terms of the list remain). Hence, if f (n) is the number of comparisons required to search for an
element in a search sequence of size n, then

f (n) = f (n/2) + 2

when n is even. ▲

EXAMPLE 2 Finding the Maximum and Minimum of a Sequence Consider the following algorithm for
locating the maximum and minimum elements of a sequence a 1 ,a 2 ,...,a n .If n = 1, then a 1 is
the maximum and the minimum. If n> 1, split the sequence into two sequences, either where
both have the same number of elements or where one of the sequences has one more element
than the other. The problem is reduced to finding the maximum and minimum of each of the
two smaller sequences. The solution to the original problem results from the comparison of the
separate maxima and minima of the two smaller sequences to obtain the overall maximum and
minimum.
Let f (n) be the total number of comparisons needed to find the maximum and minimum
elements of the sequence with n elements. We have shown that a problem of size n can be
reduced into two problems of size n/2, when n is even, using two comparisons, one to compare
the maxima of the two sequences and the other to compare the minima of the two sequences.
This gives the recurrence relation

f (n) = 2f (n/2) + 2

when n is even. ▲

EXAMPLE 3 Merge Sort The merge sort algorithm (introduced in Section 5.4) splits a list to be sorted
with n items, where n is even, into two lists with n/2 elements each, and uses fewer than n
comparisons to merge the two sorted lists of n/2 items each into one sorted list. Consequently,
the number of comparisons used by the merge sort to sort a list of n elements is less than M(n),
where the function M(n) satisfies the divide-and-conquer recurrence relation

M(n) = 2M(n/2) + n. ▲

EXAMPLE 4 Fast Multiplication of Integers Surprisingly, there are more efficient algorithms than the con-
ventional algorithm (described in Section 4.2) for multiplying integers. One of these algorithms,
which uses a divide-and-conquer technique, will be described here. This fast multiplication al-
gorithm proceeds by splitting each of two 2n-bit integers into two blocks, each with n bits.
Then, the original multiplication is reduced from the multiplication of two 2n-bit integers to
three multiplications of n-bit integers, plus shifts and additions.
Suppose that a and b are integers with binary expansions of length 2n (add initial bits of
zero in these expansions if necessary to make them the same length). Let

a = (a 2n−1 a 2n−2 ··· a 1 a 0 ) 2 and b = (b 2n−1 b 2n−2 ··· b 1 b 0 ) 2 .