Master Master Method Method Some of the slides are from Prof Plaisted s resources at University of North Carolina at Chapel Hill The Master Method Based on the Master theorem Cookbook approach for solving recurrences of the form T n aT n b f n a 1 b 1 are constants f n is asymptotically positive n b may not be an integer but we ignore floors and ceilings Requires memorization of three cases COT5407 The Master Theorem Theorem Theorem4 1 4 1 Let Letaa 11 and and bb 11be beconstants constants let letf n f n be beaafunction function and and Let LetT n T n be bedefined definedon onnonnegative nonnegativeintegers integersby bythe therecurrence recurrence T n T n aT n b aT n b f n f n where wherewe wecan canreplace replacen b n bby by n b n b or or n b n b T n T n can canbe bebounded boundedasymptotically asymptoticallyin inthree threecases cases log loga a for some constant 0 then T n nlog logaa 1 1 IfIf f n O n f n O n for some constant 0 then T n n log a 2 2 IfIf f n f n n nlog a then thenT n T n nnloglogaalglgn n log a 3 3 IfIf f n f n n nlog a for forsome someconstant constant 0 0 and andif if for forsome someconstant constantcc 11and andall allsufficiently sufficientlylarge largen n we wehave havea f n b a f n b ccf n f n then thenT n T n f n f n b b b b b b b b COT5407 b b Recursion tree view f n f n a f n b a 1 2 a a 1 1 1 a f n b 2 a 1 1 1 af n b f n b a 2 2 f n b f n b f n b f n b f n b2 2 f n b 1 f n b f n b f n b2 2 a a a 1 1 1 1 1 Total T n n COT5407 a2f n b2 2 1 log b a log b n 1 nlogba a j f n b j j 0 The Master Theorem Theorem Theorem4 1 4 1 Let Letaa 11 and and bb 11be beconstants constants let letf n f n be beaafunction function and and Let LetT n T n be bedefined definedon onnonnegative nonnegativeintegers integersby bythe therecurrence recurrence T n T n aT n b aT n b f n f n where wherewe wecan canreplace replacen b n bby by n b n b or or n b n b T n T n can canbe bebounded boundedasymptotically asymptoticallyin inthree threecases cases log loga a for some constant 0 then T n nlog logaa 1 1 IfIf f n O n f n O n for some constant 0 then T n n log a 2 2 IfIf f n f n n nlog a then thenT n T n nnloglogaalglgn n log a 3 3 IfIf f n f n n nlog a for forsome someconstant constant 0 0 and andif if for forsome someconstant constantcc 11and andall allsufficiently sufficientlylarge largen n we wehave havea f n b a f n b ccf n f n then thenT n T n f n f n b b b b b b b b COT5407 b b Master Method Examples T n 16T n 4 n a 16 b 4 nlogba nlog416 n2 f n n O nlogba O n2 where 1 Case 1 Hence T n nlogba n2 T n T 3n 7 1 a 1 b 7 3 and nlogba nlog 7 3 1 n0 1 f n 1 nlogba Case 2 Therefore T n nlogba lg n lg n COT5407 Master Method Examples T n 3T n 4 n lg n a 3 b 4 thus nlogba nlog43 O n0 793 f n n lg n nlog43 where 0 2 Case 3 Therefore T n f n n lg n T n 2T n 2 n lg n a 2 b 2 f n n lg n and nlogba nlog22 n f n is asymptotically larger than nlogba but not polynomially larger The ratio lg n is asymptotically less than n for any positive Thus the Master Theorem doesn t apply here COT5407 Master Theorem What it means Case 1 If f n O nlog a for some constant 0 then T n nlog a b b nlog a alog n Number of leaves in the recursion tree f n O nlog a Sum of the cost of the nodes at each internal level asymptotically smaller than the cost of leaves by a polynomial factor Cost of the problem dominated by leaves hence cost is nlog a b b b b COT5407 Master Theorem What it means Case 2 If f n nlog a then T n nlog alg n b b nlog a alog n Number of leaves in the recursion tree f n nlog a Sum of the cost of the nodes at each level asymptotically the same as the cost of leaves There are lg n levels Hence total cost is nlog a lg n b b b b COT5407 Master Theorem What it means Case 3 If f n nlog a for some constant 0 b and if for some constant c 1 and all sufficiently large n we have a f n b c f n then T n f n nlog a alog n Number of leaves in the recursion tree f n nlog a Cost is dominated by the root Cost of the root is asymptotically larger than the sum of the cost of the leaves by a polynomial factor Hence cost is f n b b b COT5407 9 9 08 11 Master Theorem Proof for exact powers Proof when n is an exact power of b Three steps 1 Reduce the problem of solving the recurrence to the problem of evaluating an expression that contains a summation 2 Determine bounds on the summation 3 Combine 1 and 2 COT5407 Iterative Proof of the Master Theorem Using iterative substitution let us see if we can find a pattern T n aT n b f n a aT n b 2 f n b bn a 2T n b 2 af n b f n a 3T n b 3 a 2 f n b 2 af n b f n a log b n T 1 log b n 1 i a f n b i i 0 n log b a T 1 log b n 1 i i a f n b i 0 We then distinguish the three cases as The first term is dominant Each part of the summation is equally dominant The summation is a geometric series 13 f n f n a f n b a 1 2 a a 1 1 1 a f n b 2 a 1 1 1 af n b f n b a 2 2 f n b f n b f n b f n …
View Full Document