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⁰
