Recurrence Analysis

Def 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.

Fact Three Methods for Recurrence Analysis

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.

Def 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 total cost is at most .

Master Theorem

Thrm 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 .