SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
79 views
in Examples, Exercises and Projects by (562 points)
edited by

In this article,you will get to know

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

1 Answer

0 like 0 dislike
by (562 points)
selected by
 
Best answer

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)


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...