Solving Recurrences - Master method

Solving Recurrences - Master method

Methods to solve the recurrences to get bounds on the runtime are :

1. Substitution method
2. Recursion tree
3. Master theorem

3. The master method for solving recurrences

The master theorem is a formula for solving recurrences of the form T(n) = aT (n/b)+f(n), where a ≥ 1 and b > 1 and f(n) is asymptotically positive. (Asymptotically positive means that the function is positive for all sufficiently large n.)

The master method depends on the following theorem.

In each of the three cases, we compare the function f(n) with the function n^log_b^a. The larger of the two functions determines the solution to the recurrence.

If, as in case 1, the function n^log_b ^a is the larger, then the solution is T(n) = θ(n^log_b ^a).

If, as in case 2, the two functions are the same size, we multiply by a logarithmic factor, and the solution is T (n) = θ(n^log_b ^a lg n) = θ(f (n) lg n).

If, as in case 3, the function f (n) is the larger, then the solution is T (n) = θ(f(n)).

Using the master method

To use the master method, simply determine the case (if any)  to be applied of the master theorem and write down the answer.

Examples for above three cases are given below :