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