# Problem on Master Method

In this post I am going to discuss how to use Master Method for solving the recurrence relation. If you are not familiar with the master method see the link Introduction to Master Method. Lets review the three cases of Master Method quickly.

If \(T(n) = a T(\frac{n}{b}) + f(n)\) be the given recurrence relation with \(a \ge 1, \; b \gt 1\) and \(f(n)\) is asymptotically positive. Then We compare \(n^{\log_b a}\) with \(f(n)\) and determine the solution of recurrence by following these three simple rules:

$$

T(n) =

\begin{cases}

\Theta (n^{\log_b a}), & \text{if $f(n) \lt n^{\log_b a}$ by a polynomial factor of $\epsilon$} \\[2ex]

\Theta (n^{\log_b a}\log^{k+1}n), & \text{if $f(n) = n^{\log_b a}$ by a polylog factor of $\log^{k+1}n$ } \\[2ex]

\Theta (f(n)), & \text{if $f(n) \gt n^{\log_b a}$ by a polynomial factor of $\epsilon$}

\end{cases}$$

In case 3 we required to check one more condition called regularity condition, which ensures that work done at the root \(f(n)\) is always greater than work done at the next level of the root \(af\left(\frac{n}{b}\right)\) ,i.e.,

$$\bbox[pink,5px]{a f\left(\frac{n}{b}\right) \le c f(n)}$$

**Problems on Master Method**

Solve the following recurrence relation

$$T(n) = 3 T\left(\frac{n}{2}\right) + n^2$$

**Solution**

Compare the given recurrence relation with \(T(n) = a T(\frac{n}{b}) + f(n)\) we get

$$a = 3, \;\;b = 2 \;\;and \;\;f(n) = n^2$$

Now we compute \(n^{\log_b a}\) by putting the value of \(b\) and \(a\). we get

$$n^{\log_2 3} = n^{1.58}$$

since value of \(f(n)\) which is \(n^2\) is greater than value of \(n^{\log_b a}\) which is \(n^{1.58}\) **by a polynomial factor of** \(2 – 1.58 = 0.42\) (\(\epsilon = 0.42\)).

Hence case 3 of Master Method holds. But to apply the case 3, **we need to check regularity condition also**. Regularity condition is:

**Work done at the root is greater than the work done at the next level of the root i.e.**

$$a f\left(\frac{n}{b}\right) \le c f(n)$$

$$af\left(\frac{n}{b}\right) = 3*\left(\frac{n}{2}\right) = 3*\left(\frac{n}{2}\right)^2 = \frac{3}{4} n^2$$

Clearly, this value is less than \(f(n)\) which is equal to \(n^2\). Hence the Regularity condition is also holds.

So,

$$\bbox[pink,5px]{T(n) = \Theta(n^2)}$$

Solve the following recurrence relation

$$T(n) = 4 T\left(\frac{n}{2}\right) + \log n$$

**Solution**

Compare the given recurrence relation with \(T(n) = a T(\frac{n}{b}) + f(n)\) we get

$$a = 4, \;\;b = 2 \;\;and \;\;f(n) = \log n$$

Now we compute \(n^{\log_b a}\) by putting the value of \(b\) and \(a\). we get

$$n^{\log_2 4} = n^{2}$$

since value of \(f(n)\) which is \(\log n\) is smaller than value of \(n^{\log_b a}\) which is \(n^{2}\).** Hence Case 1 is applied**. so

$$\bbox[pink,5px]{T(n) = \Theta(n^2)}$$

Solve the following recurrence relation

$$T(n) = 4 T\left(\frac{n}{2}\right) + n^2$$

**Solution**

Compare the given recurrence relation with \(T(n) = a T(\frac{n}{b}) + f(n)\) we get

$$a = 4, \;\;b = 2 \;\;and \;\;f(n) = n^2$$

Now we compute \(n^{\log_b a}\) by putting the value of \(b\) and \(a\). we get

$$n^{\log_2 4} = n^{2}$$

since value of \(f(n)\) which is \(n^2\) is equal to \(n^{\log_b a}\) which is \(n^{2}\) by polylog factor of \(1\). **Hence Case 2 is applied**. so

$$\bbox[pink,5px]{T(n) = \Theta(n^2 \log n)}$$

Solve the following recurrence relation

$$T(n) = T\left(\frac{n}{2}\right) + 2^n$$

**Solution**

Compare the given recurrence relation with \(T(n) = a T(\frac{n}{b}) + f(n)\) we get

$$a = 1, \;\;b = 2 \;\;and \;\;f(n) = 2^n$$

Now we compute \(n^{\log_b a}\) by putting the value of \(b\) and \(a\). we get

$$n^{\log_2 1} = n^{0}$$

since value of \(f(n)\) which is \(2^n\) is greater than value of \(n^{\log_b a}\) which is \(1\) **by a polynomial factor of** \(n – 0= n\) (\(\epsilon = n\)).

Hence case 3 of Master Method holds. But to apply the case 3, **we need to check regularity condition also**. Regularity condition is:

**Work done at the root is greater than the work done at the next level of the root i.e.**

$$a f\left(\frac{n}{b}\right) \le c f(n)$$

$$af\left(\frac{n}{b}\right) = 1*\left(\frac{n}{2}\right) = 1*2^{\left(\frac{n}{2}\right)} = 2^{\frac{n}{2} }$$

Clearly, this value is less than \(f(n)\) which is equal to \(2^n\). **Hence the Regularity condition is also holds**.

So,

$$\bbox[pink,5px]{T(n) = \Theta(2^n)}$$

Solve the following recurrence relation

$$T(n) =64 T\left(\frac{n}{8}\right) – n^2 \log n$$

**Solution**

Master Method **does not** applied as \(f(n)\) which is \(- n^2 \log n\) is not asymptotically positive (-ve number).

Solve the following recurrence relation

$$T(n) =2^n T\left(\frac{n}{2}\right) + n^2 $$

**Solution**

Master Method **does not** applied as **a is not a constant**.

Solve the following recurrence relation

$$T(n) =2 T\left(\frac{n}{2}\right) + \frac{n}{\log n} $$

**Solution**

Compare the given recurrence relation with \(T(n) = a T(\frac{n}{b}) + f(n)\) we get

$$a = 2, \;\;b = 2 \;\;and \;\;f(n) = \frac{n}{\log n}$$

Now we compute \(n^{\log_b a}\) by putting the value of \(b\) and \(a\). we get

$$n^{\log_2 2} = n^{1}$$

since there is non polynomial difference between value of \(f(n)\) which is \(\frac{n}{\log n}\) and \(n^{\log_b a}\) which is \(n\). Hence, Master Method **does not** applied.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.