Page 548 - Discrete Mathematics and Its Applications

8.3 Divide-and-Conquer Algorithms and Recurrence Relations 527

where b n = g(n + 1)Q(n + 1)a n , with 2 n−1

C n = n + 1 + C k
Q(n) = (f (1)f (2) ··· f(n − 1))/(g(1)g(2) ··· g(n)). n
k = 0
b) Use part (a) to solve the original recurrence relation for n = 1, 2,..., with initial condition C 0 = 0.
to obtain a) Show that {C n } also satisfies the recurrence relation
n
C + i = 1 Q(i)h(i) nC n = (n + 1)C n−1 + 2n for n = 1, 2,....
a n = . b) Use Exercise 48 to solve the recurrence relation in
g(n + 1)Q(n + 1)
part (a) to find an explicit formula for C n .
∗∗ 51. Prove Theorem 4.
∗ 49. Use Exercise 48 to solve the recurrence relation ∗∗ 52. Prove Theorem 6.
(n + 1)a n = (n + 3)a n−1 + n, for n ≥ 1, with a 0 = 1. 2
53. Solve the recurrence relation T (n) = nT (n/2) with ini-
k
50. It can be shown that C n , the average number of com- tial condition T(1) = 6 when n = 2 for some inte-
k
parisons made by the quick sort algorithm (described in ger k.[Hint: Let n = 2 and then make the substitution
k
preamble to Exercise 50 in Section 5.4), when sorting n a k = log T(2 ) to obtain a linear nonhomogeneous re-
elements in random order, satisfies the recurrence relation currence relation.]
8.3 Divide-and-Conquer Algorithms and Recurrence Relations

Introduction

Many recursive algorithms take a problem with a given input and divide it into one or more
smaller problems. This reduction is successively applied until the solutions of the smaller prob-
lems can be found quickly. For instance, we perform a binary search by reducing the search for
an element in a list to the search for this element in a list half as long. We successively apply
this reduction until one element is left. When we sort a list of integers using the merge sort, we
split the list into two halves of equal size and sort each half separately. We then merge the two
sorted halves.Another example of this type of recursive algorithm is a procedure for multiplying
integers that reduces the problem of the multiplication of two integers to three multiplications
of pairs of integers with half as many bits. This reduction is successively applied until integers
with one bit are obtained. These procedures follow an important algorithmic paradigm known
“Divide et impera”
(translation: “Divide and as divide-and-conquer, and are called divide-and-conquer algorithms, because they divide
conquer” - Julius Caesar a problem into one or more instances of the same problem of smaller size and they conquer
the problem by using the solutions of the smaller problems to find a solution of the original
problem, perhaps with some additional work.
In this section we will show how recurrence relations can be used to analyze the compu-
tational complexity of divide-and-conquer algorithms. We will use these recurrence relations
to estimate the number of operations used by many different divide-and-conquer algorithms,
including several that we introduce in this section.

Divide-and-Conquer Recurrence Relations

Suppose that a recursive algorithm divides a problem of size n into a subproblems, where each
subproblem is of size n/b (for simplicity, assume that n is a multiple of b; in reality, the smaller
problems are often of size equal to the nearest integers either less than or equal to, or greater
than or equal to, n/b). Also, suppose that a total of g(n) extra operations are required in the
conquer step of the algorithm to combine the solutions of the subproblems into a solution of
the original problem. Then, if f (n) represents the number of operations required to solve the
problem of size n, it follows that f satisfies the recurrence relation

f (n) = af (n/b) + g(n).

This is called a divide-and-conquer recurrence relation.