Master Theorem

---

In algorithm analysis, one of the most powerful tools to evaluate the time complexity of divide-and-conquer algorithms is the Master Theorem. The theorem provides a straightforward way to determine the time complexity of recurrences commonly encountered in algorithms like merge sort, quick sort, binary search, and many others.

Understanding how to apply the Master Theorem can save time and simplify the process of solving complex recurrences. In this blog, we’ll explore what the Master Theorem is, when to use it, and provide step-by-step examples to demonstrate how it works.

---

What is the Master Theorem?

The Master Theorem is a tool for analyzing divide-and-conquer recurrences. A divide-and-conquer algorithm solves a problem by:

1. Dividing the problem into smaller subproblems.
2. Conquering each subproblem (solving the subproblems recursively).
3. Combining the solutions of the subproblems to form the final result.

The general form of a divide-and-conquer recurrence is:

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

Where:

• $n$ is the size of the input.
• $a$ is the number of subproblems.
• $\frac{n}{b}$ is the size of each subproblem.
• $f(n)$ is the cost of dividing and combining the subproblems (the non-recursive work done).

The Master Theorem provides a way to solve this recurrence by comparing the growth rate of the recursive and non-recursive parts. The solution is derived by considering the relationship between $f(n)$ and $n^{{\log }_{b}a}$.

---

Master Theorem Cases

The Master Theorem divides recurrences into three cases based on the relationship between $f(n)$ and $n^{{\log }_{b}a}$.

Case 1: $f(n)=O(n^c)$, where $c<{\log }_{b}a$

• Condition: If the function $f(n)$ grows slower than $n^{{\log }_{b}a}$, the time complexity is dominated by the recursive part.
• Time Complexity: $T(n)=O(n^{{\log }_{b}a})$

Example: Consider the recurrence $T(n)=2T(n\mathrm{/}2)+n$. Here, $a=2$, $b=2$, and $f(n)=n$. We compute:

$${\log }_{b}a={\log }_{2}2=1$$

Since $f(n)=O(n)$ grows slower than $n^{{\log }_{b}a}=n^1$, this fits Case 1, and the time complexity is $T(n)=O(n)$.

Case 2: $f(n)=O(n^{{\log }_{b}a})$

• Condition: If the function $f(n)$ grows at the same rate as $n^{{\log }_{b}a}$, the time complexity is a combination of the recursive and non-recursive work.
• Time Complexity: $T(n)=O(n^{{\log }_{b}a}\log n)$

Example: Consider the recurrence $T(n)=2T(n\mathrm{/}2)+n$. Here, $a=2$, $b=2$, and $f(n)=n$. Again, we compute:

$${\log }_{b}a={\log }_{2}2=1$$

Since $f(n)=O(n)$ and $n^{{\log }_{b}a}=n^1$, this fits Case 2, and the time complexity is $T(n)=O(n\log n)$.

Case 3: $f(n)=O(n^c)$, where $c>{\log }_{b}a$

• Condition: If the function $f(n)$ grows faster than $n^{{\log }_{b}a}$, the time complexity is dominated by the non-recursive work.
• Time Complexity: $T(n)=O(f(n))$

Example: Consider the recurrence $T(n)=2T(n\mathrm{/}2)+n^2$. Here, $a=2$, $b=2$, and $f(n)=n^2$. We compute:

$${\log }_{b}a={\log }_{2}2=1$$

Since $f(n)=n^2$ and $n^2$ grows faster than $n^{{\log }_{b}a}=n^1$, this fits Case 3, and the time complexity is $T(n)=O(n^2)$.

---

When to Use the Master Theorem

The Master Theorem is a powerful and easy-to-apply tool for solving recurrences, but it has certain limitations. The Master Theorem can only be applied when the recurrence is in the form:

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

If the recurrence does not fit this form, or if the function $f(n)$ does not meet one of the conditions in the Master Theorem (e.g., if the function grows too irregularly), then you may need to use other methods such as the recursion tree method or the substitution method.

---

Examples of Master Theorem Applications

Example 1: Merge Sort

Merge Sort is a classic divide-and-conquer algorithm that divides the input array in half, recursively sorts the two halves, and then merges them.

The recurrence for Merge Sort is:

$$T(n)=2T(n\mathrm{/}2)+O(n)$$

Here, $a=2$, $b=2$, and $f(n)=n$. We compute:

$${\log }_{b}a={\log }_{2}2=1$$

Since $f(n)=O(n)$ and $n^{{\log }_{b}a}=n^1$, this fits Case 2. Therefore, the time complexity of Merge Sort is:

$$T(n)=O(n\log n)$$

Example 2: Binary Search

Binary Search is an algorithm that repeatedly divides the search interval in half to find an element in a sorted array. The recurrence for Binary Search is:

$$T(n)=T(n\mathrm{/}2)+O(1)$$

Here, $a=1$, $b=2$, and $f(n)=1$. We compute:

$${\log }_{b}a={\log }_{2}1=0$$

Since $f(n)=O(1)$ and $1=n^0$, this fits Case 1. Therefore, the time complexity of Binary Search is:

$$T(n)=O(\log n)$$

---

Conclusion

The Master Theorem is an essential tool for analyzing the time complexity of divide-and-conquer algorithms. By applying this theorem, you can efficiently determine the time complexity of recurrences without resorting to lengthy and complex recursion trees or substitution methods.

To summarize, the Master Theorem provides three key cases for analyzing recurrences:

• Case 1: $f(n)$ grows slower than $n^{{\log }_{b}a}$, so the time complexity is $O(n^{{\log }_{b}a})$.
• Case 2: $f(n)$ grows at the same rate as $n^{{\log }_{b}a}$, so the time complexity is $O(n^{{\log }_{b}a}\log n)$.
• Case 3: $f(n)$ grows faster than $n^{{\log }_{b}a}$, so the time complexity is $O(f(n))$.

Mastering the Master Theorem will help you solve recurrences efficiently and improve your algorithm design skills.

---

---