How can you solve problems through Master Theorem in Data structures and algorithm?

Question

In this article,you will get to know

1. Master Method
2. Master Theorem
3. Its various observations
4. Examples
5. Problems and solutions 

Answer 1

The Master Method

• Master Method solves the recurrences of the form T(n)=aT(n/b)+f(n)

where, a≥1 and b>1 ,f(n) is an asymptotically positive function.

• The above equation describes the running time of an algorithm that decides a problem of size n into subproblems each of size n/b. 

f(n) is the cost of dividing and combining the results of the subproblems i.e.

f(n)=D(n)+C(N)

2. Master Theorem

• Let a≥1 and b>1 be constants,let f(n) be a function,and let T(n) be defined on the non-negative integers by the recurrence
• T(n)=aT(n/b)+f(n) where f(n)=∅(n^klog^pn) ,  k≥0 and p is real number.

• Then ,T(n) can be bounded asymptotically as follows:

Case1: if a>b^k, then T(n)=∅(n^log _b​​​​​​^a)

Case2: if a=b^k

a)if p>-1 ,then T(n)=∅(n^log_ba log^p+1n)

b)if p=-1,then T(n)=∅(n^log_ba log logn)

c)if p<-1,then T(n)=∅(n^log_ba)

Case3: if a<b^k

 a) if p≥0,then T(n)=∅(n^klog^pn)

 b) if p<0,then T(n)=O(n^k)

3. Few examples

P) T(n)=3T(n/2)+n²

Solution:a=3,b=2,k=2,p=0

b^k=2²=4

⇒a<b^k 

⇒T(n)=∅(n^klog^pn) 

⇒T(n)=∅(n²log⁰n) 

⇒T(n)=∅(n²)

P:2) T(n)=4T(n/2)+n²

Solution:a=4,b=2,k=2,p=0

b^k=2²=4

⇒a=b^k=4

⇒T(n)=∅(n^log _balog^p+1n)

⇒T(n)=∅(n^log₂4log⁰⁺¹n)

⇒T(n)=∅(n²logn)

4. Few problems and solutions

P) T(n)=T(n/2)+n²

Solution:a=1,b=2,k=2,p=0

⇒b^k=2²=4

⇒a<b^k

⇒T(n)=∅(n^klog^pn)

⇒T(n)=∅(n²log⁰n)

⇒T(n)=∅(n²)

P:2) T(n)=16T(n/4)+n

Solution:a=16,b=4,k=1,p=0

⇒b^k=4¹=4

⇒a>b^k 

⇒T(n)=∅(n^log_ba) 

⇒T(n)=∅(n^log₄16) 

⇒T(n)=∅(n²)

P:3) T(n)=2T(n/2)+nlogn

Solution a=2,b=2,k=1,p=1

⇒b^k=2¹=2

⇒T(n)=∅(n^log_balog^p+1n) ⇒T(n)=∅(n^log₂2log¹⁺¹n) ⇒T(n)=∅(nlog²n)

P:4)T(n)=2T(n/2)+n/logn

Solution: T(n)=2T(n/2)+nlog^-1n

a=2,b=2,k=1,p=-1

⇒b^k=2¹=2 

⇒T(n)=∅(n^log_baloglogn) ⇒T(n)=∅(n^log₂2loglogn)

⇒T(n)=∅(n loglogn)

P:5)T(n)=7T(n/3)+n²

Solution:a=7,b=3,k=2,p=0

⇒b^k=3²=9 

⇒T(n)=∅(n^klog^pn)

⇒ T(n)=∅(n²log⁰n)

⇒ T(n)=∅(n²)

P:6)T(n)=3T(n/4)+nlogn

Solution:a=3,b=4,k=1,p=1

⇒b^k=4¹=4

⇒T(n)=∅(n^klog^pn) 

⇒T(n)=∅(n¹log¹n) 

⇒T(n)=∅(nlogn)

P:7)T(n)=√2T(n/2)+logn

Solution:a=√2=1.41≥1,b=2,k=0,p=1

⇒b^k=2⁰=1

⇒T(n)=∅(n^log_ba) 

⇒ T(n)=∅(n^log₂√2) 

⇒T(n)=∅(√n)

P:8)T(n)=3T(n/2)+n

Solution:a=3,b=2,k=1,p=0

⇒b^k=2¹=2

⇒T(n)=∅(n^log_ba)

⇒ T(n)=∅(n^log₂3)

P:9)T(n)=4T(n/2)+cn

Solution:a=4,b=2,k=1,p=0

⇒b^k=2¹=2

⇒T(n)=∅(n^log_ba) 

⇒T(n)=∅(n^log₂4) 

⇒T(n)=∅(n²)

P:10)T(n)=2T(n/2)+√n

Solution:a=2,b=2,k=1/2,p=0

⇒b^k=2¹=2 

⇒T(n)=∅(n^log_ba)

⇒ T(n)=∅(n^log₂2) 

⇒T(n)=∅(n)

---