Recurrence Analysis

Recurrence

A recurrence is an equation/inequality according to which the th term of a sequence of numbers is equal to some combination of the previous terms.

There are roughly three methods to solve recurrences:

1. Substitution Method: Guessing the closed form using substitution and then prove by induction.
2. Recursion Tree: Guessing the closed form using the recurrence tree and then prove by induction.
3. Master Theorem: Finding asymptotic bounds of some recurrences using predefined rules.

We will now introduce the last two methods.

Recursion Tree

Recursion Tree

Recursion tree is a tree where:

• Each node represents a single sub-problem along with the cost of the particular sub-problem.
• An edge from node to node means that the sub-problem represented by node calls the sub-problem represented by node .

e.g. For the recurrence where is a constant and : Note that not all leaves are in the last level, hence the total cost is at most

Master Theorem

Master Theorem

Consider , can be or .

1. If for some constant , then .
2. If , then . More generally, if for some integer , then .
3. If for some constant and if for some constant and , then .

e.g. Consider . Here , , . Hence . Therefore by second case of Master theorem we have .