Master Method

Cookbook for recursions of the type:

T (n) = a T ( n/b ) + f (n) :: a ³ 1, b > 1, f (n) asymptotically positive

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

Split  into 'a' pieces, each  piece of size 'n/b' overhead of divide and conquer is ' f (n)'

For example:

Merge-Sort T (n) = 2 T ( n/2 ) + Q (n)  :: so a = b = 2, and f (n) = Q (n)

Master theorem has three cases

1. If f (n) = O ( n ^{log_b a-e} ) for some constant e > 0, then T (n) = Q ( n ^{log_b a} )

2. If f (n) = Q ( n ^{log_b a} ), then T (n) = ( n ^{log_b a} lg n )

3. If f (n) = W ( n ^{log_b a+e} ) for some constant e > 0, AND if a f (n/b) £ c f (n) for some c < 1 and " n  ³ n₀ then: T (n) = Q ( f (n))

Note:: All three cases compare  n ^{log_b a} to f (n).

1. f (n)  £ c ( n ^{log_b a-e} )

2. c₂ ( n ^{log_b a} ) £ f (n) £ c₁ ( n ^{log_b a} )**

3. f (n) ³ c ( n ^{log_b a+e} )


** Special case multiplies by lg n

Master theorem examples:

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

n ^{log₂ 2}  = n¹

f (n) = Q (n) Þ case 2

therefore T (n) = Q ( n lg n)

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

n ^{log₃ 9} = n²

 f (n) = O ( n^2-1) Þ case 1 ( e = 1 )

therefore T (n) = Q ( n² )

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

n ^{log₄ 3}  » n^0.8

n lg n = W (n) = W ( n ^{log₄ 3+e} ) Þ case 3 ( e » 0.2 )

therefore T (n) = Q (n lg n)