Master’s Theorem

Learn Master’s Theorem to analyze divide and conquer algorithms. Understand recurrence relations, all three cases, solved examples, and time complexity.

Master’s Theorem

Master’s Theorem is an important method used to analyze the time complexity of recursive algorithms that follow the Divide and Conquer approach.

When a problem of size n is divided into smaller subproblems and solved recursively, the following recurrence relation is formed.

Standard Recurrence Form

It applies to recurrences of the form:

T(n)=aT(n/b​)+f(n)

Where:

• n → size of the problem
• a → number of subproblems
• n/b → size of each subproblem
• f(n) → cost of dividing the problem and combining the results

Basic Conditions of Master Theorem

• a≥1
• b>1
• f(n) must be a polynomial function, i.e.,

f(n)=Θ(n^d)

Steps to Apply Master Theorem

1. Identify a, b, and f(n)
2. Write f(n)=Θ(n^d)
3. Compare a with b^d
4. Apply the appropriate case

Three Cases of Master Theorem

Case 1: a<b^d

T(n)=Θ(n^d)

Meaning:
The divide + combine cost dominates the recurrence.

Example:

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

• a = 3
• b = 2
• f(n) = n² ⇒ d = 2
• b^d = 2² = 4
• 3 < 4 ⇒ Case 1

Final Answer:

T(n)=Θ(n²)

Case 2: a=b^d

T(n)=Θ(n^dlog⁡n)

Meaning:
Same amount of work is done at each level of recursion.

Example:

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

• a = 2
• b = 2
• d = 1
• b^d =2¹ =2
• a = b^d ⇒ Case 2

Final Answer:

T(n)=Θ(n log n)

Case 3: a>b^d

T(n)=Θ(n^log_b^a)

Meaning:
The recursive calls dominate the total cost.

(Regularity condition is assumed in exams)

Example:

T(n)=4T(n/2)+n

Step-by-step:

• a = 4
• b = 2
• f(n) = n ⇒ d = 1
• b^d = 2¹ = 2
• 4 > 2 ⇒ Case 3

Log _ba=log ₂4=2

Final Answer:

T(n)=Θ(n²)

Summary:

When Master Theorem Cannot Be Used

• Recurrence is not in the form aT(n/b)+f(n)
• f(n) is not polynomial
• a or b are not constants
• Unequal subproblem sizes

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1