Page 553 - Discrete Mathematics and Its Applications

532 8 / Advanced Counting Techniques

THEOREM 2 MASTERTHEOREM Letf beanincreasingfunctionthatsatisfiestherecurrencerelation

f (n) = af (n/b) + cn d

k
whenever n = b , where k is a positive integer, a ≥ 1, b is an integer greater than 1, and c
and d are real numbers with c positive and d nonnegative. Then

⎧ d d
⎪O(n ) if a< b ,
⎨
d
d
f (n) is O(n log n) if a = b ,
⎪
⎩ log a d
O(n if a> b .
b )
The proof of Theorem 2 is left for the reader as Exercises 29–33.
EXAMPLE 9 Complexity of Merge Sort In Example 3 we explained that the number of comparisons used
by the merge sort to sort a list of n elements is less than M(n), where M(n) = 2M(n/2) + n.
By the master theorem (Theorem 2) we find that M(n) is O(n log n), which agrees with the
estimate found in Section 5.4. ▲
EXAMPLE 10 Give a big-O estimate for the number of bit operations needed to multiply two n-bit integers
using the fast multiplication algorithm described in Example 4.

Solution: Example 4 shows that f (n) = 3f (n/2) + Cn, when n is even, where f (n) is the
number of bit operations required to multiply two n-bit integers using the fast multiplication
algorithm. Hence, from the master theorem (Theorem 2), it follows that f (n) is O(n log 3 ).
2
Note that log 3 ∼ 1.6. Because the conventional algorithm for multiplication uses O(n ) bit
operations, the fast multiplication algorithm is a substantial improvement over the conventional
algorithm in terms of time complexity for sufficiently large integers, including large integers
that occur in practical applications. ▲

EXAMPLE 11 Give a big-O estimate for the number of multiplications and additions required to multiply two
n × n matrices using the matrix multiplication algorithm referred to in Example 5.

Solution: Let f (n) denote the number of additions and multiplications used by the algorithm
2
mentioned in Example 5 to multiply two n × n matrices. We have f (n) = 7f (n/2) + 15n /4,
when n is even. Hence, from the master theorem (Theorem 2), it follows that f (n) is O(n log 7 ).
Note that log 7 ∼ 2.8. Because the conventional algorithm for multiplying two n × n matrices
3
uses O(n ) additions and multiplications, it follows that for sufficiently large integers n, includ-
ing those that occur in many practical applications, this algorithm is substantially more efficient
in time complexity than the conventional algorithm. ▲
THE CLOSEST-PAIR PROBLEM We conclude this section by introducing a divide-and-
conquer algorithm from computational geometry, the part of discrete mathematics devoted to
algorithms that solve geometric problems.
EXAMPLE 12 The Closest-Pair Problem Consider the problem of determining the closest pair of points
in a set of n points (x 1 ,y 1 ),...,(x n ,y n ) in the plane, where the distance between two points

2
2
(x i ,y i ) and (x j ,y j ) is the usual Euclidean distance (x i − x j ) + (y i − y j ) . This problem
arises in many applications such as determining the closest pair of airplanes in the air space at a
particular altitude being managed by an air traffic controller. How can this closest pair of points
be found in an efficient way?