Discrete Mathematics for Computer Science

Exercises 579

mn .(3k+1 - 2 k+1) (n = 2 k)

= 3m •3k - 2m .2k

The following identity can be used to simplify this expression:

3k = ( 2 10g 2 (3))k = ( 2 k)10g 2 (3) = nlog2(^3 )

Therefore, the solution is T(n) = 3m f n1°g2(^3 ) - 2mn. 0

Corollary 3 gives a solution to the recurrence for multiplying two n-bit numbers as

described earlier. Since log 2 (3) = 1.59 and the term 2mn is subtracted from 3m nlIog2(3),

the complexity of this algorithm is of the order n 1.59. The recurrence for the usual multipli-

cation algorithm has a term 4T(n/2). By replacing three by four in Corollary 3, it is seen

that the order of complexity of the usual multiplication is 0(n^2 ).

9.10.1 Complexity of Divide-and-Conquer Recurrence Relations

Often, the more important information about an algorithm is its complexity rather than an
exact formula to describe its behavior for a particular case. For the three types of divide

and conquer algorithms with the function f(n) = k where k is a constant, Table 9.1 shows

both the solution and the complexity of the solution for each of the types.

Table 9.1 Divide and Conquer Complexity

T(n) = CT(n/d) + k T(1) = k

T(n) T(n) is O(*)

C = I legal(n) + I 1Ogd (n)

C=d (dn- 1)/(d - 1)f(1) n

C : d C 0 1 (CnlIgd(C) - 1)/(C - 1)f(1) nflogd(c)

Using Theorem 1 to determine the values in Table 9.1 is often referred to as the Master
Theorem.

Exercises

1. Show that the recurrence relation an = an-=/(1 + an-1) with ao = C has the function
   S(n) = C/(1 + Cn) as a solution.


2. Find solutions for the following recurrences using back substitution, and then verify
   the correctness of these solutions by induction on k where n = dk.

(a) an = an/d +e fork> O,n =dk,d :1

(e forn =^1

(b) an = Can/d+e forCyd,C0l,k>O,n=dk

be for n =1