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

The Algorithm Forest has sent several recursive trees that look similar, hoping the Observation Tower can determine their growth rates. You must first verify whether they truly belong to the same asymptotic model.

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.

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²

n^(log₂8)=n³ and n² are 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 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.

Three Typical Examples

Binary Search

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

At the base case, the threshold a=1,b=2 and the benchmark n^0=1 fall under Case 2:

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 base case n^(log₂7) is approximately n^2.807, which exceeds 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.

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.

From Verifying the Recursive Hypothesis

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 genuinely 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

When subproblems overlap, direct recursion leads to redundant computations. Memoization caches results by parameter, transforming the recursion call graph from a tree into a directed acyclic graph (DAG). It is suitable when:

• Identical parameters genuinely 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 a memory leak; 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 baseline scenario;
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 Mathematics for Computer Science
• MIT OpenCourseWare: Introduction to Algorithms