skip to content

Memoizing an exponential recursion doesn't always make it polynomial — how do you tell in advance?

level: seniorimportance: should knowfreq 50%

answer

  1. caching removes repetition, not breadth
  2. what does one cache entry get keyed by?
  3. count the values that key can take
  4. a subset-valued key has 2^n values
  5. states times work per state

basics

~20 s

Count the distinct reachable states the cache key can take, then multiply by the work each state does outside recursion. A key holding a subset of n items has 2^n values — caching helps enormously and still leaves you exponential.

solid answer

~40 s

Cost after caching is `(number of distinct reachable states) × (work per state, excluding recursion)`, and the state count is decided entirely by what goes into the cache key. A key of `(last item placed, set of items already placed)` ranges over n · 2^n values, so the result is Θ(n^2 · 2^n) — a colossal improvement on n! but still exponential. A key of `(item index, remaining budget)` ranges over n · B values and yields O(n·B), which is polynomial in n and B, though only pseudo-polynomial in the input's encoded size. Two corrections people miss: count *reachable* states, not the full cross product of key components, and include key construction in the per-state work — hashing an n-element set costs O(n) and multiplies the whole bound.

code

pseudocode · 10 lines
pseudocode
// state: last = guest in the previous seat, placed = set already seated
best(last, placed):
  if size(placed) == n: return 0
  if (last, placed) in memo: return memo[(last, placed)]
  r = -infinity
  for g in 0..n-1:
    if g not in placed:
      r = max(r, rapport(last, g) + best(g, placed + {g}))
  memo[(last, placed)] = r
  return r

go deeper

for a junior

Recall that caching helps only when the same state recurs, and that the cost afterwards is the number of distinct states times the work each one does.

for a middle

Read a cache key and count its domain. Explain why a key holding a subset gives 2^n states while one holding an index and a remainder gives a product of small ranges.

for a senior

Do the estimate before implementing: state count, per-state work, and the memory the cache will hold, then say at which n each of those becomes the binding constraint.

for a principal

Decide between reformulating the recursion so less history matters, accepting the exponential inside a hard input cap, or switching to approximation — and make the input bound an enforced contract rather than an assumption.

## The claim being tested "Just add caching and it becomes polynomial" is one of the most durable wrong beliefs in algorithm interviews. Caching removes *repetition*; it does not remove *breadth*. If the recursion genuinely needs to distinguish exponentially many situations, then an exponential number of cache entries is exactly what an honest cache will hold, and no amount of caching discipline changes that. ## The formula total cost ≈ (distinct reachable states) × (work per state, excluding recursive calls) With memoization, each distinct state's body executes exactly once — the first visit computes it, every later visit is a lookup. So the entire analysis reduces to counting the domain of the cache key and pricing one body. This is the single most useful analytic tool for cached recursion, and it replaces recursion-tree reasoning entirely once caching is in place. ## Case one: the key contains a set Consider assigning n guests to a row of seats where a seating's score depends on adjacent pairs. To extend a partial seating you must know two things: **who** sits in the last filled seat, and **which** guests are already seated. Neither is derivable from the other, so the key is `(last, placed)`: - `last` takes n values. - `placed` is a subset of n guests: 2^n values. - States: n · 2^n. - Work per state: an O(n) loop over candidate next guests, plus O(n) to build and hash the subset key. Total: Θ(n^2 · 2^n). Compare with plain enumeration at n!. At n = 20 that is roughly 20 · 2^20 ≈ 2.1 × 10^7 states against 20! ≈ 2.4 × 10^18 orderings — eleven orders of magnitude saved. Caching was absolutely worth doing, and the result is still exponential. Both halves of that sentence are true, and candidates usually assert only one. ## Case two: the key contains a bounded number Now pick decorations subject to a total spend cap. To extend a partial choice you need only the index of the next item under consideration and how much budget remains — *which* earlier items you took is irrelevant once the remaining budget is known. The key is `(index, remaining)`: - `index`: n values. `remaining`: B+1 values. - States: n · (B+1). Work per state: O(1). Total: O(n·B). Polynomial in n and B — and here is the nuance a senior answer includes: it is only **pseudo-polynomial**, because B is a *value*, and writing B down takes about log B digits. Doubling the digits of B squares nothing but doubles the exponent's worth of magnitude, so the algorithm is exponential in the input's encoded length even while looking polynomial in the numbers. Say this out loud; it separates people who have read the definition from people who have used it. ## What actually decides it The deciding factor is **how much history the recursion must carry forward**. If a partial solution can be summarised by a small tuple of bounded quantities — an index, a count, a remainder, a small mode flag — the state space is a product of small ranges and caching lands in polynomial territory. If the future genuinely depends on the exact *set* of what has happened, the state space inherits that set's 2^n size and no key design will rescue it. Redesigning the recursion so that less history matters is the real optimisation; adding a cache to a recursion that needs full history just makes an exponential algorithm faster by a constant-ish factor per state. ## Three counting mistakes **Counting the cross product instead of reachable states.** A key of `(i, j)` with i < j has about n²/2 reachable states, not n². More dramatically, a key of `(last, placed)` is only meaningful when `last` is in `placed`, cutting the count by half. Over-counting is safe as an upper bound but can make a viable approach look impossible. **Forgetting per-state work.** The formula has two factors. A cache with 10^6 states each doing an O(n) scan is not a 10^6-operation algorithm. Key construction counts too: a set-shaped key must be built, hashed and compared, and if that is O(n) it multiplies the entire bound. **Forgetting memory.** Every distinct state visited is stored. n · 2^n entries at n = 25 is over 800 million cached values — the algorithm may be fast enough in principle and still be unrunnable because the cache doesn't fit. Time and space are both `states × per-state`, with different per-state factors, and the memory one bites first surprisingly often. ## The answer worth giving "Caching makes each distinct state cost once, so the bound is states times per-state work. Here the state has to carry the set of guests already seated, which is 2^n on its own, so we get n²·2^n — vastly better than n!, still exponential, and capped by memory around n = 22 or so. If I can reformulate so the state only needs a count rather than the full set, it collapses to polynomial; otherwise the exponential is inherent and I should be arguing about the maximum n instead."

  • If caching leaves it at n^2 * 2^n, was the caching worth doing at all?
    Enormously. Plain enumeration of orderings is n!, and at n = 20 that is about 2.4 x 10^18 against roughly 2 x 10^7 cached states — eleven orders of magnitude. It converts an impossible run into a fast one while remaining exponential, so the honest statement is 'much better, still exponential, and capped by memory somewhere around n = 22'. Refusing to cache because it stays exponential is the mirror-image mistake.
  • Why is a cost of O(n*B) called only pseudo-polynomial?
    Because B is a numeric value, not a size. The input writes B down in about log B digits, so a budget with one extra digit multiplies the state count by ten while growing the input by one character. Complexity is measured against encoded input length, and by that measure the running time is exponential — it merely looks polynomial when you treat the number itself as the input size.
  • Beyond running time, what usually stops a set-keyed cached recursion first?
    Memory. Every distinct state visited is retained, so n * 2^n entries at n = 25 is over 800 million stored values — often gigabytes before the time bound becomes the binding constraint. The same states-times-per-state formula gives the space bound with the per-entry size as the second factor, and it is worth computing both before committing to the approach.
  • What reformulation actually turns an exponential state space polynomial?
    Reducing how much history the future depends on. If the remaining decisions need only a summary — an index, a count, a remainder, a small flag — the state is a product of bounded ranges and the cache is polynomial. If they genuinely need the exact set of what has already happened, the 2^n is inherent to the problem's structure and key design cannot remove it.

saying these in an interview costs you the question

  • Says memoization always yields polynomial time
  • Counts states as the full cross product of key components
  • Ignores per-state work when quoting the bound
  • Forgets that a set-shaped key costs O(n) to hash
  • Overlooks that every cached state is also stored memory
  • Calls O(n*B) fully polynomial with no caveat

context

resolving links…