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 cases:

Case-1

Case-1 states that when $f(n)$ = $O(n^{log_ba-\varepsilon})$and constant $ε$ > 1, then the final time complexity is $T(n)$ = $\Theta(n^{log_ba})$. Here

${log_ba}$ = $log$(Number of subproblems (a) ) / log(the factor by which subproblem size reduces (b) ).

Case-2

Case-2 states that when $f(n)$ = $\Theta(n^{log_ba}.log^kn)$ and constant $ε$ > 1, then the final time complexity is $T(n)$ = $\Theta(n^{log_ba}.log^{k+1}n)$.

Case-3

Case-3 states that when $f(n)$ = $\Omega(n^{log_ba+\varepsilon})$ and constant $\varepsilon$ > 1, then the final time complexity is: $T(n)$ = $\theta( f(n))$.

Let’s understand the above cases better with a diagram.