Master Method

The master method is one way to solve recurrences. The method involves the application of one of three rules of thumb depending on whether or not certain conditions are met. Note that the method may not apply to certain recurrences.

Let the recurrence be T(n)=aT(n/b)+f(n) where a≥1 and b>1. Now,

1. if f(n)=O(nlogba-e) for some e>0, then T(n)=Θ(nlogba)
2. if f(n)=Θ(nlogba), then T(n)=Θ(nlogbalg n) [Here lg=log2]
3. if f(n)=Ω(nlogba+e) for some e>0, and if af(n/b)≤cf(n) for some c<1, then T(n)=Θ(f(n))

Example 1

Let's use the same example seen in the notes for recurrences. Consider the following algorithm which prints the nodes of a balanced binary tree:

	
print_tree(leaf(Data)) :- 
    print(Data), 
    nl.
print_tree(node(Data, LeftTree, RightTree)) :-
    print(Data),
    nl,
    print_tree(LeftTree),
    print_tree(RightTree).
	
      

A quick analysis tells us that printing a single terminal node (a leaf) is a O(1) operation. The printing of a tree which contains n nodes will involve the printing of the root node's data which is a O(1) operation, followed by the printing of two sub-trees, each of which contains at most n/2 nodes (remember the tree is balanced). This gives the following recurrence for the asymptotic analysis of the running time of the print_tree algorithm.

	
T(n)=O(1)         if n=1,
T(n)=2T(n/2)+O(1) if n>1	  
	
      

The first step in using the master method is to analyse the recurrence and this gives us;

	
a=2
b=2
f(n)=O(1)
nlog22=n1=1
	
      

If we take e=1 then f(n)=O(nlogba-e)=O(1) so by the first rule of thumb we have T(n)=Θ(n).

Example 2

As another example, consider the following recurrence which is a slight alteration of the previous one:

	
T(n)=O(1)         if n=1,
T(n)=2T(n/2)+O(n) if n>1	  
	
      

This gives us

	
a=2
b=2
f(n)=O(n)
nlog22=n1=1
	
      

Since f(n)=Θ(nlogba)=Θ(n), then by the second rule of thumb we have T(n)=Θ(n lg n).

Example 3

For the final example, consider the following recurrence which, again, is a slight alteration of the previous one:

	
T(n)=O(1)          if n=1,
T(n)=2T(n/2)+O(n2) if n>1	  
	
      

This gives us

	
a=2
b=2
f(n)=O(n2)
nlog22=n1=1
	
      

Since f(n)=Ω(n1+e) for e=1, and 2f(n/2)≤cf(n) for c=1/2, then by the third rule of thumb we have T(n)=Θ(n2).

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.