Overlapping Subproblems: Why Naive Recursion Wastes Work

What This Concept Is

Overlapping subproblems occur when several recursive branches request the same state. A recursion tree records calls; a dependency graph records distinct states and their relationships. Memoization can evaluate a state once while still examining many transitions from it. The useful bound is total local work over evaluated states, including key construction, hashing/comparison, transitions, and numeric operations.

For a unit-cost representation with constant-time state lookup, this is often O(number of states + number of candidate transitions). "There are n states" alone is not a running-time analysis. Sparse maps can avoid allocating unreachable states, but they do not make expensive transitions disappear.

Why It Matters Here

This separates three explanations: a recurrence is correct, caching removes repeated work, and the remaining computation fits the resource budget. None implies the other two. Instrumentation should count cache misses and candidate transitions separately; timing a single input does not establish a bound.

Concrete Examples

Fibonacci calls. For the direct two-call recursion with bases 0 and 1, C(0)=C(1)=1 and C(n)=1+C(n-1)+C(n-2). Thus C(n)=2F(n+1)-1: fib(5) makes 15 calls. The distinct states 0..5 number six, not 15. Memoizing reduces arithmetic operations to O(n); the bit cost of growing integers is a separate issue in the rolling-array lesson.

Rod cutting. There are n+1 remaining-length states, but state l tries l first-piece lengths when all lengths exist. Total candidates are 1+2+...+n=n(n+1)/2; the table costs O(n²) time and O(n) value cells.

Matrix chain. There are n(n+1)/2 intervals, and each nontrivial interval tries its internal splits. Summing (n-L+1)(L-1) for lengths 2..n gives (n³-n)/6 split candidates. Calling it O(n²) because the table is square misses the innermost loop.

Merge sort. On a power-of-two array with positional subarrays, the binary recursion tree has 2n-1 calls, not Θ(n log n) distinct subproblems. Its Θ(n log n) work comes from merging across log n levels. A cache of positional subarrays has no repeated states to exploit in that algorithm.

Common Confusion / Misconceptions

Hashing a newly sliced string is not automatically O(1). Prefer index pairs into fixed strings when they fully specify the state. Caching whole decision histories can retain almost all nodes of an exponential search. A hit rate of zero does not make tree DP incorrect; it simply gives no reuse speedup.

Even if each state is processed once, a subset state family can be exponential. The number of (mask, submask) pairs with submask contained in mask is 3^n, including the empty submask: each element is outside, in mask only, or in both.

How To Use It

Draw the naive call tree for a tiny input, then merge equal keys. Label each state with its loop cost. Give a reachable-state bound as well as any dense allocation bound. Count numeric sizes and output length where they can grow. When measuring memoization, clear the cache between independent cold runs and record whether input construction and reconstruction are included.

Check Yourself

Why can O(n) states require O(n²) work? What does a zero cache-hit count tell you, and what does it not tell you? Why does indexing substrings by (i,j) avoid one source of hidden copying?

Mini Drill or Application

Count rod-cutting transitions for n=4 and matrix-chain splits for n=4. Feedback: 10 and 10 respectively, from different state families. Derive the general sums and explain why matching small counts do not imply equal growth.

Read This Only If Stuck

Skiena: Fibonacci by recursion/caching and edit-distance tables. Use the local contents index through the reading guide; reconstruct one call graph instead of reading the entire chapter.