Master Theorem, Recurrences & Advanced Recurrence Solvers

The classic divide-and-conquer recurrence has the form: T(n) = a * T(n/b) + f(n), where:

- a >= 1: Number of recursive subproblems generated at each step.

- b > 1: Subproblem size reduction factor (each subproblem has size n/b).

- f(n): Time required to divide the input and combine the subproblem outputs.

The Recursion Tree Model:

At depth j of the recursion tree, there are a^j subproblems, each of size n / b^j. The work at depth j is a^j * f(n / b^j). The total tree depth is log_b n. The number of leaves at the bottom level is a^{log_b n} = n^{log_b a}.

The overall solution is dictated by the race between leaf work (n^{log_b a}) and root work (f(n)).

Standard Master Theorem requires a polynomial gap n^epsilon between f(n) and n^{log_b a}. When f(n) differs only by logarithmic factors, the extended theorem applies:

If f(n) = Theta(n^{log_b a} * log^k n):

1. If k > -1: T(n) = Theta(n^{log_b a} * log^{k+1} n).

2. If k = -1: T(n) = Theta(n^{log_b a} * log(log n)).

3. If k < -1: T(n) = Theta(n^{log_b a}).

Change of Variables (Domain Transformation):

For recurrences involving fractional powers like T(n) = 2T(sqrt(n)) + log n:

Substitute n = 2^m (so m = log_2 n and sqrt(n) = 2^{m/2}).

Define S(m) = T(2^m). Then S(m) = 2S(m/2) + m. Apply Master Theorem to S(m): a=2, b=2, m^{log_2 2} = m^1. Case 2 applies: S(m) = Theta(m log m). Substituting back m = log_2 n: T(n) = Theta(log n * log(log n)).