Apply the Master Theorem only to matching recurrences
For recurrences T(n)=aT(n/b)+f(n) with fixed a≥1 and b>1, compare f(n) with n^(log_b a). The common theorem handles polynomially smaller work, equal-scale work with logarithmic factors under the relevant version, and polynomially larger work with a regularity condition.
T(n) = 2T(n/2) + n -> Θ(n log n)
T(n) = 2T(n/2) + 1 -> Θ(n)
T(n) = 2T(n/2) + n² -> Θ(n²)
In the third example, the combine work dominates. Its regularity check succeeds because 2(n/2)² = n²/2, a fixed fraction below n².
The theorem does not directly fit T(n)=T(n-1)+n, unequal split sizes such as T(n/3)+T(2n/3), or arbitrary borderline functions. Use a recursion tree, substitution, or a more suitable theorem instead of forcing a case.
Exercise
Analyze 4T(n/2)+n, 4T(n/2)+n², and 4T(n/2)+n³. For each, identify the comparison exponent before selecting a case.
Check: your answers should be Θ(n²), Θ(n² log n), and Θ(n³), with assumptions about base cases stated.