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
YouTube Channel:
Computer Science Website:
Udemy Videos on Algortithm Analysis:
