Master Theorem

Introduction

The Master Theorem is a powerful tool for analyzing the time complexity of divide-and-conquer algorithms. It helps us solve recurrences of the form:

where:

• $n$ is the size of the problem,
• $a$ is the number of subproblems,
• $b$ is the factor by which the problem size is divided,
• $f(n)$ is the cost of dividing the problem and combining the results from the subproblems.

The Master Theorem provides a direct method to determine the asymptotic behavior of recurrences based on the relationship between $a$, $b$, and the function $f(n)$.

The Three Cases of the Master Theorem

Case 1: ${\log }_{b}a>k$

If ${\log }_{b}a>k$, then the time complexity is dominated by the recursive calls, and the solution is given by:

Example 1:

Consider the recurrence:

Here, $a=4$, $b=2$, and $f(n)=n$. We calculate ${\log }_{b}a$:

Since ${\log }_{b}a=2$ and $f(n)=n=O(n^2)$, we fall into Case 1 because ${\log }_{b}a=2>1$. Therefore, the time complexity is:

Case 2: ${\log }_{b}a=k$

If ${\log }_{b}a=k$, the behavior depends on the function $f(n)$.

Case 2.1: If $p>-1$

If $f(n)$ is asymptotically larger than $n^{{\log }_{b}a}$ (i.e., $f(n)=\Omega (n^p)$ with $p>{\log }_{b}a$), then the complexity is determined by $f(n)$, and the solution is:

Example 2:

Consider the recurrence:

Here, $a=2$, $b=2$, and $f(n)=n\log n$. We calculate ${\log }_{b}a$:

Since ${\log }_{b}a=1$ and $f(n)=n\log n=\Omega (n^1)$, we fall into Case 2.1 because $f(n)$ grows faster than $n^{{\log }_{b}a}$. Therefore, the time complexity is:

Case 2.2: If $p=-1$

If $f(n)$ is exactly $n^{{\log }_{b}a}$, then we check if $f(n)$ is polynomially bounded. In this case, the solution is:

Example 3:

Consider the recurrence:

Here, $a=2$, $b=2$, and $f(n)=n$. We calculate ${\log }_{b}a$:

Since ${\log }_{b}a=1$ and $f(n)=n=\Theta (n^1)$, we fall into Case 2.2. The solution is:

Case 2.3: If $p<-1$

If $f(n)$ grows slower than $n^{{\log }_{b}a}$, then the time complexity is determined by the recursive calls:

Case 3: ${\log }_{b}a<k$

If ${\log }_{b}a<k$, the time complexity is dominated by $f(n)$, and the solution is:

Example 4:

Consider the recurrence:

Here, $a=1$, $b=2$, and $f(n)=n^2$. We calculate ${\log }_{b}a$:

Since ${\log }_{b}a=0$ and $f(n)=n^2$, we fall into Case 3 because $f(n)$ dominates the recursive term. Therefore, the time complexity is:

Case 3.1: If $p\ge 0$

If $f(n)$ is polynomially bounded, then the time complexity is dominated by $f(n)$, and the solution is:

Case 3.2: If $p<0$

If $f(n)$ grows slower than $n^{{\log }_{b}a}$, then the solution is dominated by the recursive calls:

Summary of Master Theorem Cases

1. Case 1: If ${\log }_{b}a>k$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
2. Case 2: If ${\log }_{b}a=k$:
   • Case 2.1: If $f(n)=\Omega (n^p)$ with $p>-1$, then $T(n)=\Theta (f(n))$.
   • Case 2.2: If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$.
   • Case 2.3: If $f(n)=o(n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
3. Case 3: If ${\log }_{b}a<k$:
   • Case 3.1: If $f(n)=\Omega (n^p)$ with $p\ge 0$, then $T(n)=\Theta (f(n))$.
   • Case 3.2: If $f(n)=o(n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a})$.