Master Theorem Examples

Examples

The following are some examples of the master theorem. Let’s look at them one by one.

Example 1

This is the case of merge sort. Its time complexity is $T(n)$ = $2 T(n/2)$ + $n$.

Solution

In this example, $a$ and $b$ are both equal to 2. So, $log_ba$ = $log_22$ = 1 which means that $f(n)$ = n = $\Theta(n^{log_22}.log^0n)$. That means case 2 is applied and $T(n)$ = $\Theta(n^{log_22}.log^{0+1}n)$. Its final time complexity is $T(n)$ = $\Theta(n.log(n))$.

Example 2

This is a case of binary search. Its time complexity is $T(n)$ = $T(n/2)$ + $k$.

Solution

In this example, $a$ is equal to 1 and $b$ is equal to 2. So, $log_ba$ = $log_21$ = 0 which means that $f(n)$ = k = $\Theta(n^{log_21}.log^0n)$. That means case 2 is applied and $T(n)$ = $\Theta(n^{log_21}.log^{0+1}n)$ ...