4.3 Divide-and-Conquer Recurrence and Master Theorem: First Verify the Model, Then Apply the Result

The Master Theorem can quickly solve a class of divide-and-conquer recurrences, but it is not a universal complexity calculator that works just by looking at recursion. Before applying it, you must confirm that the number of subproblems, the reduction ratio, and the cost at each level align with the assumptions of the model.

Standard Model

Master Theorem handles:

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

where:

• a≥1: the number of subproblems;
• b>1: the size of each subproblem reduced to approximately n/b;
• f(n): the cost of splitting, merging, and other non-recursive operations.

Benchmark comparison:

n^(log_b a)

This approximates the total cost contributed by the leaves of the recursion tree.

First take n=b^k, base size 1, and T(1)=Θ(1), with a,b fixed independently of n and eventually nonnegative f(n). For general integer inputs, specify floors or ceilings and the base threshold; a result on powers alone does not settle that step.

Three Common Cases

Case 1: Leaf Side Dominates

If there exists ε>0:

f(n)=O(n^(log_b a-ε))

then:

T(n)=Θ(n^(log_b a))

Example:

T(n)=8T(n/2)+n²

The baseline is n^(log₂8)=n³, and n² is polynomially smaller, so T(n)=Θ(n³).

Case 2: Layers Are Roughly Balanced

In the standard simplified version, if:

f(n)=Θ(n^(log_b a))

then:

T(n)=Θ(n^(log_b a) log n)

Merge sort:

T(n)=2T(n/2)+Θ(n)

The baseline is n, so Θ(n log n).

A more general version can account for additional logarithmic factors, but care must be taken to use the correct version; mixing conditions from different textbooks can lead to incorrect conclusions.

Case 3: Root Work Dominates

If there exists ε>0:

f(n)=Ω(n^(log_b a+ε))

and the regularity condition holds: there exists 0<c<1, for sufficiently large n:

a f(n/b) ≤ c f(n)

then:

T(n)=Θ(f(n))

Example:

T(n)=2T(n/2)+n²

The baseline is n, n² is polynomially larger, and the regularity condition holds, so Θ(n²).

The regularity condition cannot be omitted; it prevents f(n) from oscillating wildly across different input sizes, ensuring that the total work in recursive sublayers is indeed strictly smaller than the current layer by a fixed proportion.

Here 2(n/2)²=n²/2, so choose c=1/2. This Python 3 example fixes T(1)=1 and accepts positive powers of 2 only. Its columns correspond to 8T(n/2)+n², 2T(n/2)+n, and 2T(n/2)+n²:

from functools import cache

@cache
def cost(n, a, exponent):
    if n == 1:
        return 1
    return a * cost(n // 2, a, exponent) + n**exponent

for n in [2, 4, 8]:
    print(n, cost(n, 8, 2), cost(n, 2, 1), cost(n, 2, 2))
# 2 12 4 6
# 4 112 12 28
# 8 960 32 120

Their exact solutions are 2n³−n², n(1+log₂n), and 2n²−n, respectively, as direct substitution verifies. The numeric table catches arithmetic mistakes; the asymptotic conclusions still depend on the general argument above.

Three Typical Examples

Binary Search

This analyzes the worst search path; finding a match on the first comparison takes Θ(1) in the best case.

T(n) = T(n/2) + Θ(1)

With a=1,b=2, the benchmark is n^0=1, so Case 2 applies:

T(n) = Θ(log n)

Merge Sort

T(n) = 2T(n/2) + Θ(n)

This yields Θ(n log n).

Strassen's Matrix Multiplication

T(n) = 7T(n/2) + Θ(n²)

The benchmark n^(log₂7) is approximately n^2.807, polynomially larger than n²:

T(n) = Θ(n^(log₂7))

Asymptotic advantage does not imply superior performance across all matrix sizes; constants, cache behavior, and numerical stability must still be measured empirically.

Recursion That Doesn't Fit the Master Theorem

T(n)=T(n-1)+n                 // Subproblems are not of size n/b
T(n)=T(n/3)+T(2n/3)+n        // Subproblem sizes are unequal
T(n)=2T(n/2)+n log n          // Depends on the version of the Master Theorem used
T(n)=T(√n)+1                  // The shrinking form is different
T(n)=T(n-1)+T(n-2)+1         // Fibonacci-type recurrence

These recurrences can be analyzed using techniques such as expansion, recursion trees, substitution, variable substitution, characteristic equations, or the Akra–Bazzi method. Not fitting the Master Theorem does not mean the recurrence cannot be analyzed.

For the third recurrence, take n=2^k. Level j costs n(k−j), so internal work is n(k+(k−1)+...+1)=Θ(n log²n). A log n factor grows more slowly than every fixed positive power of n, so it cannot supply Case 3’s polynomial gap.

Quicksort requires special attention to different cases:

• Worst-case partition: T(n)=T(n-1)+Θ(n)=Θ(n²);
• Ideal balance: 2T(n/2)+Θ(n)=Θ(n log n);
• Random or average-case analysis requires a probabilistic model and cannot assume each partition splits the input exactly in half.

Check Recurrence Assumptions Against the Implementation

When analyzing merge sort, if every layer copies the entire array segment, f(n) might still be linear, but with different space and constant factors. If the language's slicing produces views rather than copies, the cost changes again. Before establishing a recurrence, it's essential to verify:

• Whether subproblems overlap;
• Whether slicing creates copies or views;
• Whether merging is linear;
• Whether the input is always balanced;
• Whether parallel execution measures total work or the critical path;
• Whether base thresholds and hybrid algorithms alter behavior on small inputs.

Recursion, Memoization, and Dynamic Programming

Overlapping subproblems cause repeated work. When dependencies are already acyclic, memoization shares completed results by parameter, merging repeated states in the expanded tree into a DAG. Caching does not remove dependency cycles: if f(x) waits for its own unfinished result, use cycle detection, fixed-point methods, or a different model. Memoization suits problems where:

• Identical parameters represent the same subproblem;
• Results do not depend on hidden mutable state;
• Cache keys have stable equality semantics;
• The number of states is bounded.

Bottom-up dynamic programming fills a table in dependency order, often avoiding recursion stack overhead and improving space efficiency. While both approaches can achieve the same asymptotic complexity when solving the same recurrence, their access patterns and constant factors differ.

Caching is not free: unbounded memoization can transform a time-efficient solution into unbounded memory retention; concurrent caching introduces issues like redundant computation, lock contention, and the question of whether failed results should be cached.

A Practical Analysis Workflow

1. Select the input size n;
2. Establish the base cases;
3. Count the number and scale of each recursive subproblem;
4. Compute the non-recursive work at the current level f(n);
5. Determine whether subproblems overlap or are random;
6. Choose among expansion, tree analysis, the master theorem, or other methods;
7. Validate the conclusion using induction or upper and lower bounds;
8. Independently analyze space usage, stack depth, and actual cost models.

Completion Check

For binary search, merge sort, quick sort, and a tree traversal respectively:

1. State the assumptions required for the best, average, or worst-case scenarios;
2. Establish the recurrence relation for time complexity;
3. Determine whether Master Theorem applies;
4. Derive the asymptotic bound;
5. Specify the recursion depth and additional space usage;
6. Identify which operation in the implementation (if altered) would invalidate the recurrence.

References

• MIT 6.046: Recurrences
• MIT OpenCourseWare: Introduction to Algorithms