Recurrences and Methods for solving the recurrences
Recurrence
A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.
For example, worst-case running time T(n) of the MERGE-SORT procedure by the
recurrence
Solving recurrences
The substitution method
The recursion-tree method
The master method
The substitution method
In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct.
converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion.
each node represents the cost of a single subproblem somewhere in the set of recursive function invocations.
We sum the costs within each level of the tree to obtain a set of per-level costs, and then we sum all the per-level costs to determine the total cost of all levels of the recursion.
E.g
we create a recursion tree for the recurrence T(n) = 3T(n/4) + cn2
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
In the first case
To use the master method, we simply determine which case (if any) of the master theorem applies and write down the answer.
Example 1
Example 2
Example 3
Solve the recurrence:
( The recurrence for merge sort (excluding the base case) )
Solution
Solve the recurrence:
(describes the running time of the first divide-and-conquer algorithm for matrix multiplication)
Solution
Solve the recurrence:
(describes the running time of Strassen’s algorithm for matrix multiplication)
Solution
a = 7, b = 2, f (n) =
since, 2.80 < log 7 < 2.81
f (n) = O ( nlog 7 – e ), where e = 0.8 Case 1 applies and T (n) =
( nlog 7)
Books Referred
Introduction to Algorithms, 3rd Edition, Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Cliffort
End