Master Theorem
What is the Master Theorem?
Section titled “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
Section titled “Purpose”Use Master Theorem to directly find the Big-O time complexity without full recursion tree expansion.
Three Cases of Master Theorem
Section titled “Three Cases of Master Theorem”Compare
| Case | Condition | Result |
|---|---|---|
| Case 1 | ||
| Case 2 | ||
| Case 3 |
What is
Section titled “What is ?”It’s the cost of the recursion tree (total work across all levels).
Compare this with
Examples
Section titled “Examples”Example 1
Section titled “Example 1”, , → Case 2
Example 2
Section titled “Example 2”, , → Case 1
Example 3
Section titled “Example 3”, , , and satisfies the regularity condition → Case 3
Summary
Section titled “Summary”Compare
| Case | If | Then |
|---|---|---|
| 1 | Smaller | |
| 2 | Equal | |
| 3 | Larger + regular |