Recurrences

A recurrence is an equation that is defined in terms of itself. Recurrences are often used when analysing recursive algorithms.

Example

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	  
	
      

References

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