Big-Oh for Recursive Functions: Recurrence Relations

It's not easy trying to determine the asymptotic complexity (using big-Oh) of recursive functions without an easy-to-use but underutilized tool. This web page gives an introduction to how recurrence relations can be used to help determine the big-Oh running time of recursive functions. This material is taken from what we present in our courses at Duke University and was given at a College Board AP workshop in August of 1998 at Berkeley.

Motivation

The problem below appeared as AB Problem 3 on the 1996 AP exam, for which a C++ translation has been made.

Given a binary tree, is it a search tree?

In part A students are asked to write the function ValsLess:

struct Tree { int info; Tree * left; Tree * right; Tree(int value, Tree * lchild, Tree * rchild) : info(value), left(lchild), right(rchild) { } }; bool ValsLess(Tree * t, int val) // post: return true if and only if all values in t are less than val

In Part B, students are asked to write IsBST using ValsLess and assuming that a similar function ValsGreater exists. The solution is shown below:

bool IsBST(Tree * t) // postcondition: returns true if t represents a binary search // tree containing no duplicate values; // otherwise, returns false. { if (t == NULL) return true; // empty tree is a search tree return ValsLess(t->left,t->info) && ValsGreater(t->right,t->info) && IsBST(t->left) && IsBST(t->right); }

Before continuing you should try to determine/guess/reason about what the complexity of IsBST is for an n-node tree. Assume that ValsLess and ValsGreater both run in O(n) time for an n-node tree.

A function with similar characteristics

What is the asymptotic complexity of the function DoStuff shown below. Why? Assume that the function Combine runs in O(n) time when |left-right| = n, i.e., when Combine is used to combine n elements in the vector a.

void DoStuff(apvector<int> & a, int left,int right) // postcondition: a[left] <= ... <= a[right] { int mid = (left+right)/2; if (left < right) { DoStuff(a,left,mid); DoStuff(a,mid+1,right); Combine(a,left,mid,right); } }

You may recognize this function as an implementation of Mergesort. You may also remember that the complexity of Mergesort is O(n log n) fo an n-element array/vector. How does this relate to the function IsBST?

We'll make a mathematical definition:

The Recurrence Relation

Let T(n) be the time for DoStuff to execute on an n-element vector, i.e., when |left-right| = n. Note that the time for DoStuff to execute on a one element vector is O(1), constant time.

Then we have the following relationship:

 T(n) = 2 T(n/2) + O(n) [the O(n) is for Combine]
 T(1) = O(1) 

This relationship is called a recurrence relation because the function T(..) occurs on both sides of the = sign. This recurrence relation completely describes the function DoStuff, so if we could solve the recurrence relation we would know the complexity of DoStuff since T(n) is the time for DoStuff to execute.

Base Case

When you write a recurrence relation you must write two equations: one for the general case and one for the base case. These correspond to the recursive function to which the recurrence applies. The base case is often an O(1) operation, though it can be otherwise. In some recurrence relations the base case involves input of size one, so we wrote T(1) = O(1). However, there are cases when the bse case has size zero. In such cases the base could would be T(0) = O(1).

How does this relate to the time for IsBST to execute? If you look carefully at the code for IsBST you'll see that it has the same form as the function DoStuff, so that IsBST will have the same recurrence relation as DoStuff. This means that if you accept that DoStuff is an O(n log n) function, then IsBST is also an O(n log n) function.

Solving Recurrence Relations

You can actually solve the recurrence relation given above. We'll sketch how to do that here.

We'll write n instead of O(n) in the first line below because it makes the algebra much simpler.

 T(n) = 2 T(n/2) + n
 
 = 2 [2 T(n/4) + n/2] + n
 
 = 4 T(n/4) + 2n
 = 4 [2 T(n/8) + n/4] + 2n
 = 8 T(n/8) + 3n
 = (ask your class to fill in this line, or you fill it in)
  you should have written: 16 T(n/16) + 4n 
 = 2k T(n/2k) + k n [this is the Eureka! line]
 

You could ask students to fill in parts of the last line. Note that the last line is derived by seeing a pattern --- this is the Eureka/leap of faith/practice with generalizing mathematical patterns part of the problem.

We know that T(1) = 1 and this is a way to end the derivation above. In particular we want T(1) to appear on the right hand side of the = sign. This means we want:

 n/2k = 1 OR n = 2k OR log2 n = k

Continuing with the previous derivation we get the following since k = log₂ n:

 = 2k T(n/2k) + k n
 = 2log2 n T(1) + (log2n) n
 = n + n log2 n [remember that T(1) = 1]
 = O(n log n)

So we've solved the recurrence relation and its solution is what we "knew" it would be. To make this a formal proof you would need to use induction to show that O(n log n) is the solution to the given recurrence relation, but the "plug and chug" method shown above shows how to derive the solution --- the subsequent verification that this is the solution is something that can be left to a more advanced algorithms class.

Recurrence Relations to Remember

My suggestion is to do what we do in our classes: show students the "big five" recurrence relations below and ask them to remember what algorithms these are associated with. We ask our students to solve other recurrence relations, but we really want them to reason about recursive functions using the recurrence relations below more than knowing how to solve any given recurrence relation. We also want students to be able to derive a recurrence relation from a recursive function --- more on that later.

1. T(n) = T(n/2) + O(1)

2. T(n) = T(n-1) + O(1)

3. T(n) = 2 T(n/2) + O(1)

4. T(n) = T(n-1) + O(n)

5. T(n) = 2 T(n/2) + O(n)

Before continuing, or with your class, try to fit each of the above recurrence relations to an algorithm and thus to its big-Oh solution. We'll show what these are below. Of course for practice you can ask your students to derive the solutions to the recurrence relations using the plug-and-chug method.