Source: EECS 376 Section Notes 1, University of Michigan
Tags: recurrence relation, substitution trick, non-standard recurrence, Master Theorem workaround, EECS 376, asymptotic analysis
The Master Theorem covers recurrences where the non-recursive term is O(n^d) for some constant d. Plenty of real divide-and-conquer algorithms produce recurrences that do not fit this mould, typically because the combine work includes a log factor or some other non-polynomial term. This topic introduces the substitution trick, a technique for transforming such recurrences into a form the Master Theorem can handle. You should be comfortable with the Master Theorem itself (see Part 1) and with basic logarithm identities before working through this material.
When a recurrence has a non-polynomial combine term like O(n log n), define a new function (e.g. S(n) = T(n)/log n) that absorbs the troublesome factor, rewrite the recurrence for S(n), bound it into Master-Theorem form, solve for S(n), then substitute back to get T(n). The example covered here turns T(n) = 2T(n/2) + O(n log n) into T(n) = O(n log² n).
Substitution trick (for recurrences)
A technique where you define a new function S(n) in terms of T(n) so that the recurrence for S(n) fits the Master Theorem, even when T(n)'s recurrence does not.
Think of it as: change variables to get rid of the awkward bit, solve the nicer version, then change back.
Non-polynomial combine term
A combine-step cost such as O(n log n), O(n² log n), or O(n√n) that cannot be written as O(n^d) for any single constant d. The Master Theorem as stated in this course does not directly apply to these.
In simple terms: the overhead per level of recursion grows in a way that does not fit neatly into "n to some fixed power."
Consider the recurrence (for n > 1):
T(n) = 2T(n/2) + O(n log n)
The combine term is O(n log n), not O(n^d) for any constant d. The Master Theorem does not apply directly.
Let S(n) = T(n) / log n, so that T(n) = S(n) · log n.
The goal is to find a recurrence for S(n) that the Master Theorem can handle.
Plug T(n) = S(n) log n into the original recurrence:
S(n) · log n = 2 · S(n/2) · log(n/2) + O(n log n)
Since log(n/2) = log n - log 2, this becomes:
S(n) · log n = 2 · S(n/2) · (log n - log 2) + O(n log n)
Dividing O(n log n) by log n gives O(n). This is valid asymptotically. We get:
S(n) = 2 · S(n/2) · (1 - log 2 / log n) + O(n)
The factor (1 - log 2 / log n) is less than 1 for all n > 2. So:
S(n) ≤ 2 · S(n/2) + O(n)
This is now in standard Master Theorem form with k = 2, b = 2, d = 1.
k/b^d = 2/2 = 1, so Case 2 applies: S(n) = O(n log n).
The Master Theorem works with inequalities as well as equalities here, giving an upper bound.
T(n) = S(n) · log n = O(n log n) · log n = O(n log² n).
Identify the non-polynomial factor in the combine term (here, the extra log n).
Define S(n) = T(n) divided by that factor.
Derive a recurrence for S(n).
Bound any messy coefficients to get standard Master Theorem form.
Solve for S(n).
Multiply back to recover T(n).
Students sometimes try to apply the Master Theorem directly to T(n) = 2T(n/2) + O(n log n) by treating d as "slightly more than 1." There is no such d. The theorem requires a specific constant exponent.
When dividing both sides by log n, students worry this is not valid because log n is not a constant. Asymptotically, it is fine: O(n log n) / log n = O(n). The division is on the order class, not on a per-instance basis in a way that breaks the asymptotic bound.
Students often forget to substitute back at the end. Finding S(n) = O(n log n) is only the intermediate result. The answer is T(n) = S(n) · log n = O(n log² n), not O(n log n).
The inequality step (dropping the (1 - log 2 / log n) factor) sometimes confuses students into thinking the result is only an upper bound. For this class of problems, the upper bound from the inequality matches the actual growth rate.
⚠️ Know that T(n) = 2T(n/2) + O(n log n) solves to O(n log² n). This specific result is commonly tested.
⚠️ Be prepared to carry out the substitution trick from scratch on a similar recurrence. The steps (define S, substitute, simplify, bound, apply Master Theorem, substitute back) are the template.
⚠️ Understand why the Master Theorem cannot handle O(n log n) directly: there is no constant d such that n log n = Θ(n^d).
True or false: O(n log n) can be written as O(n^d) for some constant d. (False)
Fill in the blank: If S(n) = T(n)/log n and T(n) = O(n log² n), then S(n) = O(___). (n log n)
True or false: The substitution trick works by defining a new function that absorbs the non-polynomial factor, so the recurrence for the new function fits the Master Theorem. (True)
Fill in the blank: Dividing O(n log n) by log n gives O(___). (n)
Q: Solve T(n) = 2T(n/2) + O(n log n) using the substitution trick. State each step.
A: Define S(n) = T(n)/log n. Substituting gives S(n) log n = 2S(n/2)(log n - log 2) + O(n log n). Divide by log n: S(n) = 2S(n/2)(1 - log 2/log n) + O(n). Since (1 - log 2/log n) < 1, we bound S(n) ≤ 2S(n/2) + O(n). Master Theorem with k = 2, b = 2, d = 1 gives Case 2: S(n) = O(n log n). Therefore T(n) = S(n) log n = O(n log² n).
Q: Why can we switch from an equality to an inequality (S(n) ≤ 2S(n/2) + O(n)) and still use the Master Theorem?
A: The Master Theorem gives an asymptotic upper bound. An inequality T(n) ≤ kT(n/b) + O(n^d) still yields T(n) = O(f(n)) for the appropriate case. The bound we get is valid as an upper bound on the original recurrence.
Q: A divide-and-conquer algorithm makes 3 recursive calls on inputs of size n/3, and the combine step takes O(n√n) time. Why can the Master Theorem not be applied directly?
A: The combine step is O(n^(3/2)), which is O(n^d) with d = 3/2. This one actually can be solved directly: k = 3, b = 3, d = 3/2, k/b^d = 3/3^(3/2) = 3/(3√3) = 1/√3 < 1, Case 1: T(n) = O(n^(3/2)). The substitution trick is needed only when the combine term genuinely cannot be expressed as O(n^d) for any constant d, such as O(n log n).
This builds directly on the Master Theorem material in Part 1 of these notes. The substitution trick is one of several techniques for non-standard recurrences; others include the Akra-Bazzi theorem (a generalisation of the Master Theorem that handles non-polynomial terms natively) and the recursion tree method (unrolling the recurrence level by level and summing). The log² n result also appears in the analysis of algorithms like merge sort with non-constant merge cost and certain computational geometry divide-and-conquer algorithms.
non-Master Theorem recurrence, substitution trick, variable substitution, non-polynomial combine term, O(n log n), O(n log² n), recurrence solving, asymptotic analysis, logarithmic factor, divide and conquer, Master Theorem workaround, EECS 376, foundations of computer science, Akra-Bazzi, recursion tree, upper bound technique