# Master Theorem

Solve Recurrence Relation Using Master Theorem / Method

# How to solve a recurrence relation running time ?

## MASTER THEOREM

To solve a recurrence relation running time you can use many different techniques. One popular technique is to use the **Master Theorem** also known as the **Master Method**. “ In the analysis of algorithms, the **master theorem** provides a solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.”-Wikipedia

# EXAMPLE #1

Let’s take the example from the video above and solve it using the Master Theorem. The problem is below.

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

T(0) = 0

Using the Master Theorem, we must identify our **a,b, and d** values.

Let’s rewrite the equation to look like the Master Theorem and then identify those values.

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

= 1*T(n / (3/2) ) + n⁰so a=1, b= (3/2) , d=0

Now we just plug in our values to solve the recurrence, if 1 = (3/2)⁰ then the answer is Θ(n^d log n)= Θ(n⁰ log n) = **Θ(log n). **This means our function runtime is **Θ(log n). **We could also write it as **T(n) =** **Θ(log n).**

# EXAMPLE #2

https://www.youtube.com/user/randerson112358

Let’s take the example from the video above and solve it using the Master Theorem. The problem is below.

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

Here we assume the base case is some constant because all recurrence relations have a recursive case and a base case. so T(1) = M, where M is a constant.

Let’s rewrite the equation to identify the values A,B,D, and K.

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

T(n) = AT(n/B) + f(n)

So A= 2, B=2, f(n) = n¹ log¹ n → D=1 and K=1

**Note:** *Here I have **D=1** , because n¹ log n = n log n, which is our function. ***Note:** *Here I have **K=1**, because n log¹ n = log n*

**Note:** *In the video the variable D is called C.*

Now we check if D is greater than, less than or equal to log base b of a.

Log base b of a = log base 2 of 2 = 1 and D=1 so they are equal.

Using the case where those values are equal we can conclude that our function T(n) is **Θ(n^D log^K+1 n). **After plugging in values for D and K, we see T(n) is **Θ( n log² n).**

# EXAMPLE #3

Let’s take the example from the video above and solve it using the Master Theorem. The problem is below, and this is the recurrence of the Merge Sort algorithm.

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

Θ( n )

Here we assume the base case is some constant because all recurrence relations have a recursive case and a base case. So T(1) = M, where M is a constant.

Let’s rewrite the equation to identify the values A,B,D, and K.

Since we are given f(n) as **Θ( n ), **we can use any function that belongs to that set. I will choose f(n) = n

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

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

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

T(n) = AT(n/B) + f(n)

A=2, B=2, f(n) = n¹ → D=1, K=0

**NOTE:** The Master Theorem in the above video uses a different flavor of the Master Theorem. There is no value K. But assuming we were using the generic Master Theorem K would be equal to 0 because our function is n¹ = n¹ * 1 = n¹ * log⁰ n. Therefore log⁰n implies k=0, since log ^k n = log⁰ n.

Now we check if D is greater than, less than or equal to log base b of a.

Log base b of a = log base 2 of 2 = 1 and D=1 so they are equal.

Using the case where those values are equal we can conclude that our function T(n) is **Θ(n^D log^K+1 n). **After plugging in values for D and K, we see T(n) is **Θ( n log¹ n) = Θ( n log n) .**

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

# Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

**YouTube Channel:***randerson112358: *https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

*compsci112358:*

https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

**Website:**

http://everythingcomputerscience.com/

**Video Tutorials on Recurrence Relation:**

https://www.udemy.com/recurrence-relation-made-easy/

**Video Tutorial on Algorithm Analysis:**

https://www.udemy.com/algorithm-analysis/

**Twitter:**

https://twitter.com/CsEverything