The Master Method for Solving Recurrences

Introduction

When analyzing Divide and Conquer algorithms, we often obtain recurrence relations of the form

$$T(n)=aT(n/b)+f(n)$$

Instead of solving every recurrence using substitution or recursion trees, researchers introduces the Master Method, which provides a "cookbook" method for solving many commonly occurring recurrences. Once the three cases are memorized, many divide-and-conquer recurrences can be solved quickly.

Motivation

Many Divide and Conquer algorithms have recurrence relations of the form

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

Examples include

• Merge Sort
• Binary Search
• Strassen Matrix Multiplication
• Karatsuba Multiplication
• Closest Pair of Points

Instead of solving these recurrences by

• substitution,
• iteration, or
• recursion tree,

we can often apply the Master Theorem, which directly gives the asymptotic running time.

---

General Form

The Master Theorem applies to recurrences of the form

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

where

• $a \ge 1$ is the number of recursive subproblems,
• $b>1$ is the factor by which the problem size is reduced,
• $f(n)$ is the work done outside the recursive calls (divide and combine).

---

Meaning of Each Parameter

Suppose

$$T(n)=2T\left(\frac n2\right)+n$$

Then

• $a=2$ (two recursive calls),
• $b=2$(each subproblem has size $n\mathrm{/}\mathrm{2),}$
• $f(n)=n$(linear merge cost).

The Master Theorem

For

$$T(n)=aT(n/b)+f(n)$$

where

• $a>0$
  
• $b>1$
• $f(n)\ge0$
  

compare the driving function $f(n)$with the watershed function

$$\boxed{n^{\log_b a}}$$

The result depends on which function grows faster.

Procedure for Applying the Master Theorem

For every recurrence:

1. Write it in the form

   $$T(n)=aT(n/b)+f(n)$$
   
2. Identify $a$, $b$, and the driving function $f(n)$.

3. Compute the watershed function

   $$n^{\log_ba}$$
   
4. Compare $f(n)$ with the watershed function.
5. Determine whether Case 1, Case 2, or Case 3 applies.
6. Verify the regularity condition if you are using Case 3.
7. Write the asymptotic solution.

---

The Watershed Function

The watershed function:

$$\boxed{n^{\log_b a}}$$

This function is the reference against which the driving function $f(n)$ is compared.

---

Why is it called the Watershed Function?

Think of a watershed as a dividing line.

If

• $f(n)$ is smaller, Case 1 applies.
• $f(n)$ is approximately equal, Case 2 applies.
• $f(n)$ is larger, Case 3 applies.

Thus the watershed function separates the three cases.

Case 1

Condition

If

$$f(n)=O\!\left(n^{\log_b a-\varepsilon}\right)$$

for some

$$\varepsilon>0$$

then

$$\boxed{T(n)=\Theta\left(n^{\log_b a}\right)}$$

---

Interpretation

The recursive work dominates.

The divide/combine work is much smaller.

The cost of the leaves dominates the recursion tree.

---

Example 1

$$T(n)=9T(n/3)+n$$

Step 1

Identify

$$a=9,\qquad b=3$$

---

Step 2

Watershed

$$n^{\log_39}=n^2$$

---

Step 3

Driving function

$$f(n)=n$$

Clearly,

$$n=O(n^{2-\varepsilon})$$

Choose

$$\varepsilon=1$$

Case 1 applies.

Hence

$$\boxed{T(n)=\Theta(n^2)}$$

---

Case 2

Condition

If

$$f(n)=\Theta\left(n^{\log_b a}\log^k n\right)$$

where

$$k\ge0$$

then

$$\boxed{ T(n)= \Theta \left( n^{\log_ba} \log^{k+1}n \right) }$$

---

Interpretation

The recursive work and the driving function are balanced.

Every level of the recursion tree contributes approximately the same cost.

Since there are $\Theta(\log n)$ levels, one extra $\log n$ factor appears.

---

Example 1 (Merge Sort)

$$T(n)=2T(n/2)+n$$

Step 1

$$a=2,\qquad b=2$$

---

Step 2

Watershed

$$n^{\log_22}=n$$

---

Step 3

Driving function

$$f(n)=n$$

Exactly equal.

Therefore

Case 2.

Result

$$\boxed{\Theta(n\log n)}$$

This is the Merge Sort analysis 

---

Example 2

$$T(n)=2T(n/2)+n\log n$$

Watershed

$$n$$

Driving function

$$n\log n = \Theta(n\log^1 n)$$

Therefore

Case 2

Answer

$$\boxed{\Theta(n\log^2n)}$$

---

Case 3

Condition

If

$$f(n)= \Omega \left( n^{\log_ba+\varepsilon} \right)$$

and

$$af(n/b)\le cf(n)$$

for some

$$c<1,$$

then

$$\boxed{T(n)=\Theta(f(n))}$$

---

Regularity Condition

Case 3 requires one additional condition:

$$af(n/b)\le cf(n)$$

This ensures that the driving function decreases sufficiently as the recursion proceeds.

Note that this condition is satisfied by most polynomially bounded functions encountered in algorithm analysis.

---

Example

$$T(n)=3T(n/4)+n\log n$$

Here,

$$a=3,\qquad b=4$$

Watershed

$$n^{\log_43}\approx n^{0.793}$$

Driving function

$$n\log n$$

which is polynomially larger.

Regularity condition:

$$3\left(\frac n4\log\frac n4\right) \le \frac34n\log n$$

Hence Case 3 applies.

Final answer:

$$\boxed{\Theta(n\log n)}$$

---

Summary of the Three Cases

Case	Comparison	Result
Case1	$f(n)$is polynomially smaller than the watershed function	$\Theta(n^{\log_ba})$
Case2	$\mathrm{ \; f}(n)\; matches\; the\; watershed\; function\; up\; to\; a\; polylogarithmic\; factor$	$\mathrm{ \; \; \; \; \Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$
Case3	$\mathrm{ \; f}(n)\; is\; polynomially\; larger\; than\; the\; watershed\; function\; and \; satisfies\; the\; regularity\; condition$	$\mathrm{ \; \; \; \; \Theta }(f(n))$