Recursive Algorithms Complexity
Internal
Overview
The running time of recursive algorithms can be analyzed using recurrences.
Recurrence
A recurrence, or a recurrence equation, is an equation or an inequality that describe the running time of a recursive algorithm for a problem of size n in terms of the running time on smaller inputs. Once the running time is expressed this way, we can use mathematical tools or other methods to solve the recurrence, which means obtaining asymptotic bounds on the running time of the algorithm.
Solving Recurrences
There are at least three method to solve recurrences:
Substitution Method
The method consists in guessing a bound and then using mathematical induction on the recurrence to prove the solution correct. We can guess a solution using a recursion tree. Examples on how to use mathematical induction to prove the bound is correct are available in CLRS page 83.
Recursion-Tree Method
The method consists in converting the recurrence into graphical tree representation whose nodes represent costs incurred at various level of the recursion. After we lay out the tree, we sum the costs within each level of the tree to obtain a set of per-level costs, then we sum all the per-level costs to determine the total cost of the recursion. The bound such guessed can be proven with the substitution method. Examples on how to build recursion trees are available in CLRS page 37 and page 88.
The Master Method (Master Theorem)