gen-briefly-explain-the-master-theorem-and-one-common-misconcept-5de1

Briefly explain the master theorem and one common misconception about it.

## The Master Theorem The Master Theorem provides a cookbook method for solving recurrence relations of the form: **T(n) = aT(n/b) + f(n)** where a ≥ 1, b > 1, and f(n) is asymptotically positive. It compares f(n) to n^(log_b(a)) and gives the solution based on which dominates: - **Case 1**: If f(n) = O(n^(log_b(a) - ε)) for some ε > 0, then T(n) = Θ(n^(log_b(a))) - **Case 2**: If f(n) = Θ(n^(log_b(a))), then T(n) = Θ(n^(log_b(a)) log n) - **Case 3**: If f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0, AND a·f(n/b) ≤ c·f(n) for some c < 1 (regularity condition), then T(n) = Θ(f(n)) ## Common Misconception **The "gap" problem**: Many people assume the Master Theorem covers all recurrences of this form, but there's actually a **gap between the cases**. For example, T(n) = 2T(n/2) + n·log(n) falls in this gap—f(n) is only slightly larger than n^(log_2(2)) = n, but not polynomially larger (no ε exists). The Master Theorem simply doesn't apply here, and you need other methods like the Akra-Bazzi theorem or recursion tree analysis.