Master Theorem

randerson112358

May 17, 2018·5 min read

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 !

Introduction to Algorithm Analysis [For Complete Beginners]

Understand and solve algorithms using Big O, Big Omega, and Theta time complexity.

www.udemy.com

Recurrence Relation Made Easy | Udemy

A guide to solving any recursion program, or recurrence relation.

www.udemy.com

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 )