University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

The Master Method

Works for recurrences of the form:

T(n) = a * T( n/b ) + f(n)

What is the idea?

Suppose you split the problem of size n into "a" problems of size "n/b" (ideally you want to split them into "a" problems of size "n/a"). Therefore, the running time for the problem of size n is "a" times a problem of size "n/b" plus some function to integrate the subproblems f(n).

The method consists in comparing f(n) with the function n ^{lg b a}

Master Theorem

Let a>=1 and b>1 . ..constants

f(n) ... a function

let T(n) be defined as:

  T(n) = a* T(n/b) + f(n)

where n/b is either floor or ceiling of n/b

Then, T(n) can be bounded asymptotically as follows:

1. If  f(n) = O (n ^{lg b a-s}) for some constant s>0 ... Then T(n)=Teta(n ^{lg b a})
2. If f(n) = Teta(n ^{lg b a} ) ... then T(n)= Teta( n ^{lg b a} *  lg n )
3. If f(n) = Omega(n^{lg b a+s})   for some constant s>0 ...  AND      if a * f(n/b) <= c* f(n) for some constant c<1 and large n,   then T(n) = Teta(f(n))

Notes:

factor s, indicates polymomially smaller or larger

Examples:

T(n) = 9* T(n/3) + n

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

T(n) = 3*T(n/4)+n*lg n

T(n) = 2*T(n/2) + n*lg n