Scribd
Upload
83 views8 pages

Master Method: Proof (Part II)

1. The document discusses the master method for analyzing recursive algorithms. It examines three cases where the method can be applied. 2. Case 1 involves algorithms where the work at each level is constant. Case 2 examines algorithms where the work grows slower than the number of subproblems. Case 3 looks at algorithms where the work grows faster than the number of subproblems. 3. For all three cases, the master method provides tight asymptotic bounds on the running time that are independent of the input size. It also offers intuitive insights into the overall work done by the algorithms.

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
83 views8 pages

Master Method: Proof (Part II)

1. The document discusses the master method for analyzing recursive algorithms. It examines three cases where the method can be applied. 2. Case 1 involves algorithms where the work at each level is constant. Case 2 examines algorithms where the work grows slower than the number of subproblems. Case 3 looks at algorithms where the work grows faster than the number of subproblems. 3. For all three cases, the master method provides tight asymptotic bounds on the running time that are independent of the input size. It also offers intuitive insights into the overall work done by the algorithms.

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  II)  
Design  and  Analysis  
of  Algorithms  I  
The  Story  So  Far/Case  1   =  1  for  
all  j  
•     
=1  

=  (logbn  +  1)  

[  end  Case  1  ]  
Tim  Roughgarden  
Basic  Sums  Fact  
For                ,  we  have    

Proof  :  by  inducKon  (you  check)  


Upshot:  
1.  If  r<1  is  constant,  RHS  is  <=        =  a  constant  

2.  If  r>1  is  constant,  RHS  is  <=  


Tim  Roughgarden  
Case  2   :=  r  

•     

<=    a  constant  
(  independent  of  n)  
[  by  basic  sums  fact  ]  
[  total  work  dominated  by  top  level  ]  

Tim  Roughgarden  
Case  3   :=  r  >  1  

•     

<=    constant  *  
largest  term  

Tim  Roughgarden  
Level  0   a  children  

Level  1   Tem
ver

Level  logbn   #  of  leaves  =    

The  number  of  levels  of  the  recursion  tree.  


The  number  of  nodes  of  the  recursion  tree.  

The  number  of  edges  of  the  recursion  tree.  


Case  3  conKnued  
•     

More  intuiKve  
Simpler  to  apply  

[End  Case  3]  

Tim  Roughgarden  
The  Master  Method  
•     

Tim  Roughgarden  

You might also like