Substitution Method

The substitution method is one way to solve recurrences. The method involves making an educated guess, then using mathematical induction to prove that the guess holds.

Example

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	  
	
      

We make an initial guess that T(n)≤cn for some c, that is to say T(n)=O(n). We now try to prove it with mathematical induction. Our induction hypothesis is the assumption that the result holds for all m<n and we try to prove that it holds for n. This can be done by substituting the assumed result in the original recurrence.

	
T(n) = 2T(n/2)+1
     = 2(cn/2)+1 [by induction hpothesis as n/2<n]
     = cn+1
	
      

But as we see the result does not hold as cn+1≤cn is obviously false. What we can do is try to prove the stronger claim that T(n)≤cn-a for some c and a. From this we get:

	
T(n) = 2T(n/2)+1
     = 2(cn/2-a)+1 [by induction hpothesis as n/2<n]
     = cn-2a+1
	
      

This does hold as cn-2a+1≤cn for all a≥1, so T(n)=O(n).

References

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