Recurrences: Substitution, Recursion Tree, Master Theorem

What This Concept Is

A recurrence separates the cost of recursive calls from local work. Specify the input size, base cases, rounding, and counted operation before solving it. For example, mergesort's comparison-and-move work satisfies T(n)=T(floor(n/2))+T(ceil(n/2))+Theta(n) for n>=2 with constant base cost. Copying slices or processing large integers can change the implementation's cost model.

Three useful methods are substitution (prove a guessed bound by induction), a recursion tree (sum work across levels and leaves), and a theorem whose hypotheses match the recurrence. A numeric plot suggests a conjecture; it does not prove one.

Why It Matters Here

The same branching structure can have very different cost if the combine step changes. 2T(n/2)+n is Theta(n log n), while 2T(n/2)+n² is Theta(n²). Conversely, overlapping recursive calls can repeat work; memoization changes the computation graph and therefore the recurrence being analyzed.

Concrete Examples

A complete recursion-tree calculation

Let n be a power of two, T(1)=1, and T(n)=2T(n/2)+n. At level j there are 2^j nodes, each doing n/2^j local work. Every internal level costs n. There are log2(n) such levels and n leaves costing one each, so T(n)=n log2(n)+n exactly. At n=8 the result is32. Substitution checks the equality directly and includes the base case.

For unequal splits T(n)=T(floor(n/2))+T(floor(n/3))+n, use constant base cost below2. Total size at the next level is at most5/6 of the current total, so internal work is at most n*sum((5/6)^j) <= 6n. There are O(n) leaves (the number at the deepest possible level is at most n), and the root alone costs n. Thus T(n)=Theta(n). Levels near the bottom are truncated; saying every level costs exactly n*(5/6)^j would be false.

The polynomial-gap Master Theorem

For T(n)=aT(n/b)+f(n), constant a>=1,b>1, suitable nonnegative f and constant-size base cases, set d=log_b(a). One common form is:

Condition	Conclusion
f(n)=O(n^(d-epsilon)) for some epsilon>0	Theta(n^d)
f(n)=Theta(n^d log^k(n)), fixed k>=0	Theta(n^d log^(k+1)(n))
f(n)=Omega(n^(d+epsilon)) and af(n/b)<=cf(n) eventually for some c<1	Theta(f(n))

Case3 requires both a polynomial gap and regularity. For 2T(n/2)+n²/log(n) with a base case below4, the gap above n exists and the regularity ratio tends to1/2; it does not provide a counterexample to regularity. The values of a and b matter.

A recurrence outside that form

Let T(2)=1 and T(n)=2T(n/2)+n/log2(n) for powers of two n>=4. Write n=2^m. Internal level j costs n/(m-j), for j=0..m-2. Leaves cost n/2. Consequently

T(n) = n*(1/m + 1/(m-1) + ... + 1/2) + n/2
     = Theta(n log log n).

Here f is below n but not polynomially below n, so Case1 fails; Case2's k>=0 restriction fails; Case3 is irrelevant because f is not polynomially larger. A more general theorem can cover it, but this tree already gives a proof.

Common Confusion / Misconceptions

• Two samples determine the recurrence class. Functions can agree at every sampled point and differ afterward. An arbitrary callable f cannot be classified by sampling two sizes. Restrict a symbolic exercise to a declared family and verify hypotheses algebraically.
• A branch halves, so the algorithm is logarithmic. Count all branches and local work. Mergesort halves size and still does Theta(n log n) total work.
• Ignore base cases. Leaves can dominate, as in 4T(n/2)+n, whose answer is Theta(n²).
• Master Case3 just means f is larger. A logarithmic factor is not a polynomial gap, and regularity is a separate obligation.

How To Use It

Write the domain and base cases. Derive the recurrence from executed calls. Guess a bound using a tree, then prove matching upper/lower bounds or use a theorem with all hypotheses stated. Handle floors and ceilings explicitly or explain why the cited theorem permits them. Include leaf work and memory separately from total time.

Transfer / Where This Shows Up Later

Sorting, search, inversion counting, and multiplication use these tools. Later DP lessons count distinct states and transitions instead of treating repeated recursive calls as independent new subproblems. A runtime guarantee must describe the implementation's operations, not just its mathematical recurrence.

Check Yourself

1. Why does T(n)=T(n-1)+1, T(0)=0, give n rather than log n? There are n unit decrements.
2. Why can T(n)=4T(n/2)+n be Theta(n²)? Its leaves already number n² on power-of-two inputs.
3. Why does the n/log(n) example require a harmonic sum? Level costs change as the remaining depth shrinks.

Mini Drill or Application

Solve 3T(n/3)+n, T(1)=1 on powers of three, and T(n)=T(n-1)+n, T(0)=0. Give exact expressions and matching asymptotic bounds. Solutions: n log3(n)+n; n(n+1)/2. Then change the first combine cost to n² and explain why the root levels dominate.

Read This Only If Stuck

In CLRS, locate substitution, recursion trees, and the Master Theorem. In The Algorithm Design Manual, use divide-and-conquer and recurrence analysis. Editions and generated chunk boundaries differ; these are book-index links, not claims about exact section destinations.