CMSC 435 Algorithm Analysis & Design

 

Lecture 3

The Master Method for solving Divide & Conquer Recurrence Relations

 

1.      Mergesort  --  Consider a list of n items to be sorted in non-decreasing order.

Adopt the following (recursive) strategy:

1.      Divide the list in half

2.      Spawn two processes to sort the two halves

3.      Merge the two sorted halves.

When merging the two halves, worst case, every item in the second half of the

list is greater than all items in the first half of the list except for the last item

which is the greatest item in the original list.  A merge will require that the first item of the second half of the list be compared with all n/2 items in the first half before it is placed in the merged list.  The remaining n/2 –1 items in the second

half are then compared with the last card of the first half before the merged list is completed.  The total number of compares in the last merge (worst case) is

therefore n/2 + (n/2 – 1) = n – 1.

 

If we let T(n) = the number of compares to mergesort a list of n items, then

 

            T(n) = 2T(n/2) + n-1

 

2.      Binary Search

Strategy:  Recursively divide the list in half, compare the key with the item

At the front of the second half of the list.  If the key is greater than or equal to this element, binary search the second half of the list, else binary search the first half of the list.

 

If we let T(n) = the number of compares to binarysearch a list of n items, then

 

            T(n) = T(n/2) + 1

 

3.      The Master Method

These two algorithms have recurrence relations of the form

 

            T(n) = a T(n/b) + f(n)                where a ³ 1 and b > 1

and there exists an n0 such that

f(n) >0  for all n ³ n0

            Theorem – (Master Theorem)

            Let a ³ 1 and b > 1 be constants, let f(n) be an asymptotically nonnegative

Function, and let T(n) be defined on the nonnegative integers by the recurrence

 

            T(n) = aT(n/b) + f(n)

 

Where we interpret n/b to mean either ën/bû or én/bù .  Then T(n) can be

Bounded asymptotically as follows:

1.      If  f(n) = O(nlogba - e) for some constant e > 0, then T(n) = Q(nlogba)

2.      If  f(n) = Q (nlogba), then T(n) = Q (nlogba lg n)

3.      If  f(n) = W(nlogba + e) for some constant e > 0, and if af(n/b) £ cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Q(f(n))

 

4.      Examples

T(n) = 4T(n/2) + n

 

Then a = 4, b = 2, f(n) = n

We see that logb a = log2 4 = 2  and nlogba = n2

We need to show that

                                    f(n) = O(nlogba - e)

choose e = ½  Then  there exists a pair  c, n0 such that 

 

                        n < c n3/2          for all n:  n ³ n0

 

(for c = 1, n0 = 2  the inequality is obviously satisfied)

Thus  T(n) = Q (n2)

 

T(n) = 4T(n/2) + n3

 

Then a = 4, b = 2, f(n) = n3

We see that logb a = log2 4 = 2  and nlogba = n2

We need to show that

                                    f(n) = W(nlogba + e)

choose e = ½  Then  there exists a pair  c, n0 such that 

 

                        n3 > c n5/2         for all n:  n ³ n0

 

(for c = 1, n0 = 2  the inequality is obviously satisfied)

Next we need to show that there exists a c < 1 such that for all sufficiently large n,

 

                        a f(n/b) £ c f(n)             choose c = 5/8

then

                        4 (n/2)3 £ 5/8 n3

                        n3/2 £ 5/8 n3                             true, found a satisfatory c

 

Thus  T(n) = Q (n3)

 

In deciding which case to apply when using the Master Method, always compare nlogba with f(n) as your first step.  If f(n) is O(nlogba) then apply case 1, if it is big theta or big omega apply case 2 or 3.