Master theorem (analysis of algorithms)

The Master Theorem provides a cookbook solution for recurrence relations that arise in the analysis of divide-and-conquer algorithms. Specifically, it provides asymptotic bounds (using Big O, Big Theta, and Big Omega notation) for recurrences of the form:

T(n) = aT(n/b) + f(n)

where:

• T(n) is the time complexity of the problem of size n.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. We assume all subproblems have roughly equal size.
• f(n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and combining the solutions.

The theorem compares f(n) with n^(log_b a) (referred to as the "critical case"). Depending on the relationship between these two functions, the Master Theorem states one of three possible asymptotic bounds for T(n).

Three Cases of the Master Theorem

Let k be a constant.

• Case 1: If f(n) = O(n^(log_b a - k)) for some constant k > 0, then T(n) = Θ(n^(log_b a)). In simpler terms, if f(n) grows polynomially slower than n^(log_b a), then T(n) is dominated by the cost of solving the subproblems.

• Case 2: If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) * log n). If f(n) grows at roughly the same rate as n^(log_b a), then we multiply the growth rate by a logarithmic factor.

• Case 3: If f(n) = Ω(n^(log_b a + k)) for some constant k > 0, and if af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n (the "regularity condition"), then T(n) = Θ(f(n)). In simpler terms, if f(n) grows polynomially faster than n^(log_b a) and satisfies the regularity condition, then T(n) is dominated by the cost of the work done outside the recursive calls.

Limitations

The Master Theorem cannot be applied to every recurrence relation. Some limitations include:

• Recurrences where a or b are not constants.
• Recurrences where f(n) is not polynomially comparable to n^(log_b a). This includes cases where f(n) contains logarithmic factors raised to powers greater than one in Case 2, or logarithmic factors in the first term in Case 1 and Case 3.
• Recurrences where the regularity condition in Case 3 does not hold.

When the Master Theorem is not applicable, other methods such as the substitution method or the recursion tree method can be used to solve the recurrence relation.