Iteration Method

The iteration method is one way to solve recurrences. The method involves iteratively expanding the recurrence until it can be expressed in terms of the argument variable.

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	  
	
      

We start expanding the recurrence:

	
T(n) = 2T(n/2)+1
     = 2(2T(n/4)+1)+1
     = 2(2(2T(n/8)+1)+1)+1
     = 2(2(2(2T(n/16)+1)+1)+1)+1
     = 8(2T(n/16)+1)+4+2+1
     = 16T(n/16)+8+4+2+1
	
      

The i^th term in the expansion is 2i(n/2i). When i=log2n, we have

	
n/2i = n/2log2n
	
      

and because of the logarithmic identity 2log2n=n we get:

	
T(n/2log2n) = T(1) = 1
	
      

The point i=log2n is the base case of our recursion. Expanding to this point we get:

	
T(n) = 2log2n+ ... +8+4+2+1
     = ∑log2ni=02i
     < 2log2(n+1)
     = n+1
	
      

So T(n) = O(n).

Example 2

As another example, consider the following recurrence:

	
T(1) = 1
T(n) = 4T(n/5)+n
	
      

When we expand we get the following:

	
T(n) = 4T(n/5)+n
     = n + 4T(n/5)
     = n + 4(n/5 + 4T(n/25))
     = n + 4(n/5 + 4(n/25 + 4T(n/125)))
     = n + 4n/5 + 16n/25 + 64n/125 + ...
	
      

Now T(n/5i)=1 when i=log5n, so

	  
T(n) = n+4n/5+16n/25+64n/125+ ... +4log5n
     = n∑log5ni=0(4/5)i+4log5n 
     = n∑log5ni=0(4/5)i+nlog54
	  
	

So T(n)=O(n) as both n∑log5ni=0(4/5)i=O(n) and nlog54=O(n).

References

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