**Master’s Theorem-**

Master’s Theorem is a popular method for solving the recurrence relations. |

Master’s theorem solves recurrence relations of the form-

where a >= 1, b > 1, k >= 0 and p is a real number

**Solving Recurrence Relations-**

To solve recurrence relations using Master’s theorem, we compare a with b^{k}.

Then, we follow the following cases-

**Case-01:**

If a > b^{k}, then T(n) = θ (n^{logba})

**Case-02:**

If a = b^{k }and

- If p < -1, then T(n) = θ (n
^{logba}) - If p = -1, then T(n) = θ (n
^{logba}.log^{2}n) - If p > -1, then T(n) = θ (n
^{logba}.log^{p+1}n)

**Case-03:**

If a < b^{k }and

- If p < 0, then T(n) = O (n
^{k}) - If p >= 0, then T(n) = θ (n
^{k}log^{p}n)

**PRACTICE PROBLEMS BASED ON MASTER’S THEOREM-**

**Problem-01:**

Solve the following recurrence relation using Master’s theorem-

T(n) = 3T(n/2) + n^{2}

**Solution-**

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (n^{k}log^{p}n)

we have-

a = 3

b = 2

k = 2

p = 0

Now, a = 3 and b^{k} = 2^{2} = 4.

Clearly, a < b^{k}

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (n^{k}log^{p}n)

T(n) = θ (n^{2}log^{0}n)

Thus,

T(n) = θ (n^{2}) |

**Problem-02:**

Solve the following recurrence relation using Master’s theorem-

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

**Solution-**

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (n^{k}log^{p}n)

we have-

a = 2

b = 2

k = 1

p = 1

Now, a = 2 and b^{k} = 2^{1} = 2.

Clearly, a = b^{k}

So, we follow case-02.

Since p = 1, so we have-

T(n) = θ (n^{logba}.log^{p+1}n)

T(n) = θ (n^{log22}.log^{1+1}n)

Thus,

T(n) = θ (nlog^{2}n) |

**Problem-03:**

Solve the following recurrence relation using Master’s theorem-

T(n) = 2T(n/4) + n^{0.51}

**Solution-**

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (n^{k}log^{p}n)

we have-

a = 2

b = 4

k = 0.51

p = 0

Now, a = 2 and b^{k} = 4^{0.51} = 2.0279.

Clearly, a < b^{k}

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (n^{k}log^{p}n)

T(n) = θ (n^{0.51}log^{0}n)

Thus,

T(n) = θ (n^{0.51}) |

**Problem-04:**

Solve the following recurrence relation using Master’s theorem-

T(n) = √2T(n/2) + logn

**Solution-**

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (n^{k}log^{p}n)

we have-

a = √2

b = 2

k = 0

p = 1

Now, a = √2 = 1.414 and b^{k} = 2^{0} = 1.

Clearly, a > b^{k}

So, we follow case-01.

So, we have-

T(n) = θ (n^{logba})

T(n) = θ (n^{log2√2})

T(n) = θ (n^{1/2})

Thus,

T(n) = θ (√n) |

**Problem-05:**

Solve the following recurrence relation using Master’s theorem-

T(n) = 8T(n/4) – n^{2}logn

**Solution-**

- The given recurrence relation does not correspond to the general form of Master’s theorem.
- So, it can not be solved using Master’s theorem.

**Problem-06:**

Solve the following recurrence relation using Master’s theorem-

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

**Solution-**

- We can write the given recurrence relation as T(n) = 3T(n/3) + n.
- This is because in the general form, we have θ for function f(n) which hides constants in it.
- Now, we can easily apply Master’s theorem.

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (n^{k}log^{p}n)

we have-

a = 3

b = 3

k = 1

p = 0

Now, a = 3 and b^{k} = 3^{1} = 3.

Clearly, a = b^{k}

So, we follow case-02.

Since p = 0, so we have-

T(n) = θ (n^{logba}.log^{p+1}n)

T(n) = θ (n^{log33}.log^{0+1}n)

T(n) = θ (n^{1}.log^{1}n)

Thus,

T(n) = θ (nlogn) |

**Problem-07:**

Form a recurrence relation for the following code and solve it using Master’s theorem-

A(n) { if(n<=1) return 1; else return A(√n); }

**Solution-**

- We can write a recurrence relation for the given code as T(n) = T(
**√**n) + 1. - Here 1 = Constant time taken for comparing and returning the value.
- We can not directly apply Master’s Theorem on this recurrence relation.
- This is because it does not correspond to the general form of Master’s theorem.
- However, we can modify and bring it in the general form to apply Master’s theorem.

Let-

n = 2^{m} ……(1)

then-

T(2^{m}) = T(2^{m/2}) + 1

Now, let T(2^{m}) = S(m), then T(2^{m/2}) = S(m/2)

So, we have-

S(m) = S(m/2) +1

Now, we can easily apply Master’s Theorem.

On comparing the given recurrence relation with-

S(m) = aS(m/b) + θ (m^{k}log^{p}m)

we have-

a = 1

b = 2

k = 0

p = 0

Now, a = 1 and b^{k} = 2^{0} = 1.

Clearly, a = b^{k}

So, we follow case-02.

Since p = 0, so we have-

S(m) = θ (m^{logba}.log^{p+1}m)

S(m) = θ (m^{log21}.log^{0+1}m)

S(m) = θ (m^{0}.log^{1}m)

Thus,

S(m) = θ(logm) ……(2)

Now,

- From (1), we have n = 2
^{m}. - So, logn = mlog2 which implies m = log
_{2}n.

Substituting in (2), we get-

S(m) = θ(loglog_{2}n)

Or

T(n) = θ (loglog_{2}n) |

To gain better understanding about Master’s Theorem,

**Next Article-** **Recursion Tree**

Get more notes and other study material of **Design and Analysis of Algorithms**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.