DOC PREVIEW
FIU COT 5407 - Master Method

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

FIU COT 5407 - Master Method

Download Master Method
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Master Method and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Master Method 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?