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

0 like 0 dislike
376 views

edited

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

### For Indian Students- INR 360/- || For International Students- \$9.99/-

S.No.

Course Name

Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence || Labeled as Highest Rated Course by Udemy

Apply Coupon

2.

Complete Machine Learning & Data Science with Python| ML A-Z Apply Coupon

3.

Complete Python Programming from scratch | Python Projects Apply Coupon

0 like 0 dislike
by (562 points)
selected

# 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)

1. ## 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)=∅(nklogpn) ,  k≥0 and p is real number.
• Then ,T(n) can be bounded asymptotically as follows:

Case1: if a>bk, then T(n)=∅(nlog b​​​​​​a)

Case2: if a=bk

a)if p>-1 ,then T(n)=∅(nlogba logp+1n)

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

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

Case3: if a<bk

a) if p≥0,then T(n)=∅(nklogpn)

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

1. ## Few examples

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

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

bk=22=4

⇒a<b

⇒T(n)=∅(nklogpn)

⇒T(n)=∅(n2log0n)

⇒T(n)=∅(n2)

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

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

bk=22=4

⇒a=bk=4

⇒T(n)=∅(nlog balogp+1n)

⇒T(n)=∅(nlog24log0+1n)

⇒T(n)=∅(n2logn)

1. ## Few problems and solutions

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

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

⇒bk=22=4

⇒a<bk

⇒T(n)=∅(nklogpn)

⇒T(n)=∅(n2log0n)

⇒T(n)=∅(n2)

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

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

⇒bk=41=4

⇒a>bk

⇒T(n)=∅(nlogba

⇒T(n)=∅(nlog416

⇒T(n)=∅(n2)

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

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

⇒bk=21=2

⇒T(n)=∅(nlogbalogp+1n) ⇒T(n)=∅(nlog22log1+1n) ⇒T(n)=∅(nlog2n)

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

⇒bk=21=2

⇒T(n)=∅(nlogbaloglogn) ⇒T(n)=∅(nlog22loglogn)

⇒T(n)=∅(n loglogn)

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

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

⇒bk=32=9

⇒T(n)=∅(nklogpn)

⇒ T(n)=∅(n2log0n)

⇒ T(n)=∅(n2)

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

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

⇒bk=41=4

⇒T(n)=∅(nklogpn)

⇒T(n)=∅(n1log1n)

⇒T(n)=∅(nlogn)

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

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

⇒bk=20=1

⇒T(n)=∅(nlogba

⇒ T(n)=∅(nlog2√2

⇒T(n)=∅(√n)

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

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

⇒bk=21=2

⇒T(n)=∅(nlogba)

⇒ T(n)=∅(nlog23)

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

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

⇒bk=21=2

⇒T(n)=∅(nlogba

⇒T(n)=∅(nlog24

⇒T(n)=∅(n²)

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

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

⇒bk=21=2

⇒T(n)=∅(nlogba)

⇒ T(n)=∅(nlog22

⇒T(n)=∅(n)