Example Problems - Master Method

 

Example 1

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

Solution

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

Critical function

$$n^{\log_21}=1$$

Since

$$f(n)=1=\Theta(1)$$

Case 2

Answer

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

(Binary Search)

Example 2

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

Critical function

$$n^{\log_23} =n^{1.585}$$

Since

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

Case 1

Answer

$$\boxed{\Theta(n^{1.585})}$$

Example 3

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

Critical function

$$n$$

Here,

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

This matches Case 2 with $k=1$.

Answer

Example 4 (Strassen's Matrix Multiplication)

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

Here,

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

Critical function

$$n^{\log_27} \approx n^{2.807}$$

Since

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

Case 1

Answer

$$\boxed{\Theta(n^{\log_27})\approx\Theta(n^{2.81})}$$

This is exactly why Strassen's algorithm is asymptotically faster than the classical $O(n^3)$

O(n^3) matrix multiplication algorithm.

Example 5

$$T(n)=16T(n/4)+n$$

Solution

$$a=16,\quad b=4$$

Watershed

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

Driving function

$$n$$

Case 1

Answer

Example 6

$$T(n)=25T(n/5)+n^2$$

Solution

$$a=25$$
$$b=5$$

Watershed

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

Driving function

$$n^2$$

Exactly equal

Case 2

Answer

Example 7

$$T(n)=27T(n/3)+n^2$$

Solution

Watershed

$$n^{\log_327} = n^3$$

Driving function

$$n^2$$

Case 1

Answer

Example 8

$$T(n)=8T(n/2)+n^3$$

Watershed

$$n^{\log_28} = n^3$$

Equal

Case 2

Answer

Example 9

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

Watershed

$$n^2$$

Driving

$$n^2\log n$$

Case 2

Answer

Example 10

$$T(n)=9T(n/3)+n^2\log^3n$$

Watershed

$$n^2$$

Driving

$$n^2\log^3n$$

Case 2

Answer

Example 11

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

Watershed

$$n^{\log_23} = n^{1.585}$$

Driving

$$n^2$$

Case 3

Answer

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

Example 12

$$T(n)=5T(n/2)+n^4$$

Watershed

$$n^{\log_25} = n^{2.322}$$

Driving

$$n^4$$

Case 3

Answer

$$\boxed{\Theta(n^4)}$$

​Example 13

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

Step 1: Identify
$a$,
$b$, and
$f$$($$n$$)$

$$a=2,\qquad b=4,\qquad f(n)=1$$

---

Step 2: Find the watershed function

$$n^{\log_4 2}$$

Since

$$\log_4 2=\frac12$$

Therefore,

$$n^{\log_42}=n^{1/2}$$

---

Step 3: Compare $f(n)$ with the watershed function

Driving function

$$f(n)=1$$

Watershed

$$n^{1/2}$$

Clearly,

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

Choose

$$\varepsilon=\frac14$$

---

Step 4: Determine the case

Case 1

---

Final Answer

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

​

Example:14

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

Step 1

$$a=2,\qquad b=4,\qquad f(n)=\sqrt n$$

---

Step 2

Watershed

$$n^{\log_42} =n^{1/2} =\sqrt n$$

---

Step 3

Driving function

$$\sqrt n$$

Exactly equals the watershed function.

---

Step 4

Case 2

Here

$$k=0$$

---

Final Answer

$$\boxed{T(n)=\Theta(\sqrt n\log n)}$$

​

Example - 15

$T(n)=2T(n/4)+\sqrt n\,\log^2 n$

Step 1

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

---

Step 2

Watershed

$$n^{\log_42} =\sqrt n$$

Step 3

Driving function

$$\sqrt n\log^2 n$$

This is

$$\Theta \left( n^{1/2}\log^2 n \right)$$

---

Step 4

Case 2

because

$$k=2$$

---

Final Answer

$$\boxed{T(n)=\Theta(\sqrt n\log^3 n)}$$

​

Example-16

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

Step 1

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

---

Step 2

Watershed

$$n^{1/2}$$

---

Step 3

Driving function

$$n$$

Clearly,

$$n=\Omega(n^{1/2+\varepsilon})$$

Choose

$$\varepsilon=\frac12$$

---

Step 4

Check the regularity condition

We need

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

Compute

$$2f(n/4) = 2\left(\frac n4\right) =\frac n2$$

Since

$$\frac n2 \le \frac12n$$

Choose

$$c=\frac12<1$$

Regularity condition holds.

---

Step 5

Case 3

---

Final Answer

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

Example - 17

(e) $T(n)=2T(n/4)+n^2$

Step 1

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

---

Step 2

Watershed

$$n^{1/2}$$

---

Step 3

Driving function

$$n^2$$

Clearly,

$$n^2 = \Omega (n^{1/2+\varepsilon})$$

Choose

$$\varepsilon=1$$

---

Step 4

Check regularity

$$2f(n/4) = 2\left(\frac n4\right)^2 = \frac{n^2}{8}$$

Since

$$\frac{n^2}{8} \le \frac18n^2$$

Choose

$$c=\frac18<1$$

Regularity condition holds.

---

Step 5

Case 3

---

Final Answer

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

​​​​​​