Scribd
Upload
77 views7 pages

Master Method for Recurrence Analysis

The document introduces the Master Method for analyzing divide-and-conquer recursive algorithms. It assumes a recurrence relation of the form T(n) = aT(n/b) + f(n), where a and b are constants and f(n) is the work done at each level of the recursion tree. It explains that the recursion tree has logbn levels, with b subproblems of size n/b at each level. The total work is computed by summing the work at each level of the tree, which is af(n/b).

Uploaded by

Fuzzy Assassin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
77 views7 pages

Master Method for Recurrence Analysis

The document introduces the Master Method for analyzing divide-and-conquer recursive algorithms. It assumes a recurrence relation of the form T(n) = aT(n/b) + f(n), where a and b are constants and f(n) is the work done at each level of the recursion tree. It explains that the recursion tree has logbn levels, with b subproblems of size n/b at each level. The total work is computed by summing the work at each level of the tree, which is af(n/b).

Uploaded by

Fuzzy Assassin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Master

 Method  
Proof  (Part  I)  
Design  and  Analysis  
of  Algorithms  I  
The  Master  Method  
•     
Preamble  
Assume  :  recurrence  is  
I.      (  For  some  
constant  c  )  
II.     
And  n  is  a  power  of  b.  
(general    case  is  similar,  but  more  tedious  )  

Idea  :  generalize  MergeSort  analysis.  


   (i.e.,  use  a  recursion  tree  )  
Tim  Roughgarden  
Tem
ver
What  is  the  paJern  ?  Fill  in  the  blanks  in  the  following  
statement:  at  each  level  j  =  0,1,2,…,logbn,  there  are  <blank>  
subproblems,  each  of  size  <blank>  
#  of  Umes  you  can  divide  n  by  b  
before  reaching  1  
The  Recursion  Tree  
a  braches  
       Level  0  

       Level  1  
.  
.  
.   Base  cases  
.   (size  1)  
Level  logbn

Tim  Roughgarden  
Work  at  a  Single  Level  
Total  work  at  level  j  [ignoring  work  in  recursive  calls]  

Tim  Roughgarden  
Total  Work  
Summing  over  all  levels  j  =  0,1,2,…,  logbn  :  

               Total  
               work  

Tim  Roughgarden  

You might also like