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)$. Its final time complexity is $T(n)$ = $\Theta(log(n))$.

Example 3

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

Solution

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

Example 4

In this example, an algorithm has a time complexity of $T(n)$ = 2$T(n/2)$ + $n^2$.

Solution

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