Master Theorem

Master Theorem

By definition, the master theorem is used to solve recurrence relations. It is stated as $T(n)$ = $a$ $T(n/b)$ + $f(n)$ where, a ≥ 1 and b > 1. In this relation, $n$ is the size of the input and $a$ is the number of subproblems in the recursion. $b$ is the factor by which the size of the subproblem is reduced in each recursive call. Lastly, $f(n)$ is the cost of dividing the problem into subproblems and merging the individual solutions of the subproblems into the solution.

We generally have three cases in the master theorem. In other words, we determine an asymptotic tight bound in the following three ...