Solve Recurrence Relation Using Master Theorem / Method
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) + 1T(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 )
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:
