Master Theorem
Data Structures & Algorithms
2nd Semester
What is the Master Theorem?
The Master Theorem helps you find the time complexity of many recursive algorithms of the form:
Where:
→ number of recursive calls → size reduction in each recursive call → cost outside the recursive calls (e.g., sorting, merging)
Purpose
Use Master Theorem to directly find the Big-O time complexity without full recursion tree expansion.
Three Cases of Master Theorem
Compare
| Case | Condition | Result |
|---|---|---|
| Case 1 | ||
| Case 2 | ||
| Case 3 |
What is
It’s the cost of the recursion tree (total work across all levels).
Compare this with
Examples
Example 1
, , → Case 2
Example 2
, , → Case 1
Example 3
, , , and satisfies the regularity condition → Case 3
Summary
Compare
| Case | If | Then |
|---|---|---|
| 1 | Smaller | |
| 2 | Equal | |
| 3 | Larger + regular |