Master Theorem

randerson112358
May 17, 2018 · 5 min read

Solve Recurrence Relation Using Master Theorem / Method

Image for post
Image for post
https://math.stackexchange.com/q/646908

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.

Image for post
Image for post

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:
Note:

Note:

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 !

Image for post
Image for post

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:
https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ


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

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store