gen-define-the-master-theorem-and-give-one-short-worked-example-89c9

Define the master theorem and give one short worked example.

# Master Theorem The **Master Theorem** provides a solution for recurrence relations of the form: **T(n) = aT(n/b) + f(n)** where: - a ≥ 1 (number of subproblems) - b > 1 (factor by which problem size is divided) - f(n) is the cost of work done outside recursive calls ## Three Cases Let c = log_b(a). Then: 1. **Case 1**: If f(n) = O(n^(c-ε)) for some ε > 0, then **T(n) = Θ(n^c)** 2. **Case 2**: If f(n) = Θ(n^c), then **T(n) = Θ(n^c log n)** 3. **Case 3**: If f(n) = Ω(n^(c+ε)) for some ε > 0, and af(n/b) ≤ kf(n) for some k < 1 (regularity condition), then **T(n) = Θ(f(n))** ## Worked Example **Merge Sort**: T(n) = 2T(n/2) + n - a = 2, b = 2, f(n) = n - c = log₂(2) = 1 - Compare f(n) = n with n^c = n¹ = n - Since f(n) = Θ(n^c), we're in **Case 2** **Solution: T(n) = Θ(n log n)** ✓