Master Theorem in Design and Analysis of Algorithms (DAA)

---

❮ Previous    Next ❯

---

---

Learning Objectives

After completing this tutorial, students will be able to:

• Understand the concept of Master Theorem.
• Solve recurrence relations using Master Theorem.
• Identify values of a, b and f(n).
• Apply Case 1, Case 2 and Case 3 correctly.
• Analyze Divide and Conquer algorithms efficiently.
• Determine the time complexity without lengthy calculations.
• Prepare for AKTU examinations and placement interviews.

---

Prerequisites

Before studying Master Theorem, students should be familiar with the following topics:

• Recurrence Relations
• Asymptotic Notations
• Big-O, Big-Ω and Big-Θ
• Divide and Conquer Strategy
• Logarithms
• Exponent Rules

---

What is Master Theorem?

The Master Theorem is a mathematical formula used to determine the asymptotic running time of recurrence relations having the following standard form:

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

where

• a = Number of recursive subproblems
• b = Factor by which the problem size is divided
• f(n) = Cost of work performed outside recursive calls

If a recurrence relation satisfies this form, the Master Theorem can be applied directly to obtain the time complexity.

---

Need of Master Theorem

Without Master Theorem, solving recurrence relations often requires substitution, recursion tree or iteration methods, which can be lengthy and time-consuming. Master Theorem provides a shortcut to determine the time complexity in just a few steps.

• Reduces lengthy mathematical calculations.
• Provides direct asymptotic complexity.
• Useful for Divide and Conquer algorithms.
• Frequently used in algorithm analysis.
• Saves time during examinations.

---

General Form of Master Theorem

The recurrence relation must be written in the following standard form:

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

Symbol	Meaning
a	Number of recursive calls
b	Division factor (b > 1)
n	Input size
f(n)	Work performed outside recursive calls

---

Conditions for Applying Master Theorem

Master Theorem can only be applied when the recurrence satisfies the following conditions.

• The recurrence must be of the form T(n)=aT(n/b)+f(n).
• a ≥ 1
• b > 1
• Subproblems must be of equal size.
• The problem should follow Divide and Conquer.
• f(n) should be asymptotically positive.

---

Applications of Master Theorem

Master Theorem is used to analyze the time complexity of many popular Divide and Conquer algorithms.

• Merge Sort
• Binary Search
• Strassen Matrix Multiplication
• Karatsuba Multiplication
• Closest Pair of Points
• Many Divide and Conquer Algorithms

---

Three Cases of Master Theorem

Master Theorem consists of three different cases depending upon the relationship between f(n) and n^log_ba.

Case	Condition	Result
Case 1	f(n) is smaller	Recursive work dominates
Case 2	Both are equal	Balanced work
Case 3	f(n) is larger	Outside work dominates

---

Workflow for Solving Master Theorem Problems

1. Write the recurrence in standard form.
2. Identify the values of a, b and f(n).
3. Calculate n^log_ba.
4. Compare f(n) with n^log_ba.
5. Select the correct case.
6. Write the final asymptotic complexity.

---

Flowchart of Applying Master Theorem

The following flowchart illustrates the step-by-step procedure for solving recurrence relations using Master Theorem.

---

---

---

Case 1 of Master Theorem

Case 1 applies when the work performed outside the recursive calls is asymptotically smaller than the total work performed by the recursive calls.

If

f(n) = O(n^{log_ba - ε})

where ε > 0

then

T(n) = Θ(n^log_ba)

---

Example 1

Solve the recurrence relation

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

Step 1

Identify the values.

Parameter	Value
a	2
b	2
f(n)	1

Step 2

Calculate

n^log₂2=n

Step 3

Since

1 = O(n^1-ε)

Case 1 is applicable.

Answer

T(n)=Θ(n)

---

Case 2 of Master Theorem

Case 2 applies when the work outside recursion and recursive work are asymptotically equal.

If

f(n)=Θ(n^log_ba log^kn)

where k ≥ 0

then

T(n)=Θ(n^log_ba log^k+1n)

---

Example 2

Solve

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

Step 1

Parameter	Value
a	2
b	2
f(n)	n

Step 2

Compute

n^log₂2=n

Step 3

Since

f(n)=Θ(n)

Both expressions are equal. Therefore, Case 2 is applicable.

Answer

T(n)=Θ(n log n)

---

Case 3 of Master Theorem

Case 3 applies when the work outside recursion dominates the recursive work.

If

f(n)=Ω(n^log_ba+ε)

where ε > 0 and the regularity condition is satisfied,

then

T(n)=Θ(f(n))

---

Example 3

Solve

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

Step 1

Parameter	Value
a	2
b	2
f(n)	n²

Step 2

Calculate

n^log₂2=n

Step 3

Since

n² = Ω(n^1+ε)

Case 3 is applicable.

Answer

T(n)=Θ(n²)

---

Quick Comparison of All Three Cases

Case	Condition	Result
Case 1	f(n) is smaller than nlogba	Θ(nlogba)
Case 2	f(n) equals nlogba	Θ(nlogba log n)
Case 3	f(n) is larger than nlogba	Θ(f(n))

---

Decision Making Steps

1. Write the recurrence in standard form.
2. Identify a, b and f(n).
3. Compute n^log_ba.
4. Compare f(n) with n^log_ba.
5. Select Case 1, Case 2 or Case 3.
6. Write the final Θ() complexity.

---

Flow of Solving Master Theorem

---

---

---

Regularity Condition

Before applying Case 3 of the Master Theorem, the following regularity condition must also be satisfied.

af(n/b) ≤ cf(n)

where

• 0 < c < 1
• n is sufficiently large.

This condition ensures that the work performed outside recursion grows significantly faster than the recursive work.

---

When Master Theorem Cannot Be Applied

Master Theorem is not applicable in the following situations.

• Recursive subproblems are of unequal sizes.
• Recurrence relation is not in the standard form.
• Problem does not follow Divide and Conquer.
• f(n) is not asymptotically positive.
• Regularity condition fails in Case 3.

---

Common Mistakes While Applying Master Theorem

• Incorrectly identifying the values of a and b.
• Comparing f(n) incorrectly with n^log_ba.
• Ignoring logarithmic terms.
• Applying the theorem to non-standard recurrence relations.
• Ignoring the regularity condition in Case 3.
• Writing the final answer without showing intermediate steps.

---

Applying Master Theorem to Divide and Conquer Algorithms

Many Divide and Conquer algorithms generate recurrence relations of the form

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

The Master Theorem can be directly applied to determine their time complexity.

---

1. Binary Search

Recurrence Relation

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

Parameter	Value
a	1
b	2
f(n)	1
nlogba	1
Case	Case 2
Time Complexity	Θ(log n)

---

2. Merge Sort

Recurrence Relation

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

Parameter	Value
a	2
b	2
f(n)	n
nlogba	n
Case	Case 2
Time Complexity	Θ(n log n)

---

3. Strassen Matrix Multiplication

Recurrence Relation

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

Parameter	Value
a	7
b	2
f(n)	n²
nlog27	n2.807
Case	Case 1
Time Complexity	Θ(n2.807)

---

4. Karatsuba Multiplication

Recurrence Relation

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

Parameter	Value
a	3
b	2
f(n)	n
nlog23	n1.585
Case	Case 1
Time Complexity	Θ(n1.585)

---

5. Closest Pair of Points

Recurrence Relation

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

Parameter	Value
a	2
b	2
Case	Case 2
Time Complexity	Θ(n log n)

---

6. Convex Hull (Divide and Conquer)

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

Using Case 2,

Θ(n log n)

---

7. Maximum Subarray (Divide and Conquer)

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

Applying Case 2,

Θ(n log n)

---

Summary of Divide and Conquer Algorithms

Algorithm	Recurrence Relation	Master Theorem Case	Time Complexity
Binary Search	T(n)=T(n/2)+1	Case 2	Θ(log n)
Merge Sort	T(n)=2T(n/2)+n	Case 2	Θ(n log n)
Strassen Matrix Multiplication	T(n)=7T(n/2)+n²	Case 1	Θ(n²·⁸⁰⁷)
Karatsuba Multiplication	T(n)=3T(n/2)+n	Case 1	Θ(n¹·⁵⁸⁵)
Closest Pair	T(n)=2T(n/2)+n	Case 2	Θ(n log n)
Convex Hull	T(n)=2T(n/2)+n	Case 2	Θ(n log n)
Maximum Subarray	T(n)=2T(n/2)+n	Case 2	Θ(n log n)

---

Decision Tree for Applying Master Theorem

---

---

---

Solved Examples Using Master Theorem

Example 1

Solve

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

Step	Solution
a	4
b	2
f(n)	n
nlog₂4	n²
Applicable Case	Case 1
Time Complexity	Θ(n²)

---

Example 2

Solve

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

Step	Solution
a	8
b	2
f(n)	n³
nlog₂8	n³
Applicable Case	Case 2
Time Complexity	Θ(n³ log n)

---

Example 3

Solve

T(n)=9T(n/3)+n³

Step	Solution
a	9
b	3
f(n)	n³
nlog₃9	n²
Applicable Case	Case 3
Time Complexity	Θ(n³)

---

Master Theorem Cheat Sheet

Comparison	Case	Result
f(n) is Smaller	Case 1	Θ(nlogba)
Equal	Case 2	Θ(nlogba log n)
Greater	Case 3	Θ(f(n))

---

Quick Steps to Solve Any Problem

1. Write the recurrence in standard form.
2. Identify a, b and f(n).
3. Calculate n^log_ba.
4. Compare f(n) with n^log_ba.
5. Select the appropriate case.
6. Write the Θ() complexity.

---

AKTU Previous Year Questions

1. State and explain the Master Theorem.
2. Explain all three cases of the Master Theorem with suitable examples.
3. Solve T(n)=2T(n/2)+n using Master Theorem.
4. Solve T(n)=4T(n/2)+n² using Master Theorem.
5. Solve T(n)=3T(n/2)+n using Master Theorem.
6. Find the time complexity of Merge Sort using Master Theorem.
7. Find the time complexity of Binary Search using Master Theorem.
8. Write the limitations of the Master Theorem.
9. Explain the regularity condition in Case 3.
10. Differentiate between Recurrence Relation and Master Theorem.

---

Viva Questions

1. What is the Master Theorem?
2. Why is the Master Theorem used?
3. What is Divide and Conquer?
4. What is a recurrence relation?
5. What do the symbols a and b represent?
6. What does f(n) represent?
7. How many cases are there in the Master Theorem?
8. When is Case 1 applicable?
9. When is Case 2 applicable?
10. When is Case 3 applicable?
11. What is the regularity condition?
12. Can Master Theorem solve every recurrence relation?
13. Why can't it solve unequal subproblems?
14. Which algorithms commonly use Master Theorem?
15. What is the complexity of Merge Sort?

---

Interview Questions

1. Explain the Master Theorem with examples.
2. How do you determine which case is applicable?
3. What are the limitations of the Master Theorem?
4. Explain the recurrence relation of Merge Sort.
5. Explain Binary Search using Master Theorem.
6. Why does Merge Sort belong to Case 2?
7. Why does Strassen Matrix Multiplication belong to Case 1?
8. Explain the regularity condition with an example.
9. When should Recursion Tree Method be preferred over Master Theorem?
10. Can Quick Sort always be solved using Master Theorem?

---

Multiple Choice Questions (MCQs)

Question	Answer
1. Master Theorem is mainly used to solve ______.	Recurrence Relations
2. Master Theorem is applicable to which paradigm?	Divide and Conquer
3. T(n)=2T(n/2)+n belongs to ______.	Case 2
4. Binary Search has complexity ______.	Θ(log n)
5. Merge Sort has complexity ______.	Θ(n log n)
6. Strassen Matrix Multiplication belongs to ______.	Case 1
7. Case 3 requires ______.	Regularity Condition
8. Karatsuba Algorithm complexity is ______.	Θ(n1.585)
9. Number of cases in Master Theorem is ______.	3
10. Master Theorem provides ______ complexity.	Asymptotic

---

Practice Problems

1. Solve T(n)=4T(n/2)+n.
2. Solve T(n)=2T(n/2)+n².
3. Solve T(n)=9T(n/3)+n.
4. Solve T(n)=8T(n/2)+n³.
5. Solve T(n)=3T(n/3)+n.
6. Find the complexity of Strassen Matrix Multiplication.
7. Find the complexity of Karatsuba Multiplication.
8. Explain why Binary Search belongs to Case 2.
9. Compare the three cases of Master Theorem.
10. Write an algorithm for solving recurrence relations using Master Theorem.

---

Key Takeaways

• Master Theorem is the fastest technique for solving Divide and Conquer recurrence relations.
• Always identify a, b and f(n) first.
• Compute n^log_ba before selecting a case.
• There are only three cases in the Master Theorem.
• Binary Search, Merge Sort, Strassen Matrix Multiplication, Karatsuba Multiplication, Closest Pair, Convex Hull and Maximum Subarray can all be analyzed using the Master Theorem.
• Do not apply the theorem to recurrence relations that do not satisfy its standard form.
• Remember the regularity condition while applying Case 3.

---

Summary

The Master Theorem is one of the most powerful techniques in Design and Analysis of Algorithms for solving recurrence relations generated by Divide and Conquer algorithms. It provides a direct method to determine asymptotic time complexity without expanding the recurrence relation manually. By identifying the values of a, b and f(n), computing n^log_ba, and comparing the results, students can easily determine whether Case 1, Case 2 or Case 3 is applicable. Master Theorem is extensively used to analyze algorithms such as Binary Search, Merge Sort, Strassen Matrix Multiplication, Karatsuba Multiplication, Closest Pair of Points, Convex Hull and Maximum Subarray. A strong understanding of this theorem is essential for AKTU semester examinations, GATE, placement interviews and competitive programming.

---

---

❮ Previous    Next ❯

---