When does adding a memo table to a divide-and-conquer recursion buy you nothing?
answer
- Ask what the cache is keyed on
- Count distinct keys versus total calls
- Disjoint halves never regenerate a subrange
- Every lookup misses; only writes happen
- No repeated subproblem, no payoff
basics
~20 sMemoization pays only when the same subproblem recurs. A recursion that splits its input into disjoint parts produces a distinct key on every call, so every lookup misses and you pay memory plus bookkeeping for zero saved work.
solid answer
~50 sCaching is the mechanism; repeated subproblems are the precondition. In a split-and-combine recursion the two children cover disjoint parts of the input, so no parameter tuple is ever reachable along two different paths — the table gets one write per call and never serves a hit. What you gain is nothing; what you pay is `O(number of calls)` extra memory alive for the whole run, a lookup and an insert per node, and one more thing that can be wrong (a key that omits a parameter the answer depends on returns a stale wrong result). The test to run before adding a cache: name the parameters the recursive function takes, bound how many distinct tuples are reachable from the top call, and compare that to the number of calls. Memoize only when calls vastly exceed distinct tuples.
code
pseudocode · 14 linesmemo = empty table
process(lo, hi):
if memo contains (lo, hi):
return memo[(lo, hi)]
if hi - lo == 1:
result = summarize(record[lo])
else:
mid = (lo + hi) / 2
result = combine(process(lo, mid), process(mid, hi))
memo[(lo, hi)] = result
return result
... top call is process(0, length(record))go deeper
Be ready to say what has to be true before a cache helps: the same subproblem must come up more than once. Name one recursion where it does not — a split into disjoint halves.
Explain the counting argument out loud: distinct reachable parameter tuples versus number of calls, and why an exponential tree over a small parameter space forces repeats. Name the costs a useless memo adds.
Show that you check before you cache. Interviewers expect you to notice a memo that never hits in someone's code, and to know that an incomplete cache key produces silently wrong answers rather than a crash.
Own the framing that overlap is a property of the chosen recurrence, not of the problem. Choosing a formulation with a small, heavily revisited state space is the design decision; the table is an implementation detail.
## The one test that separates the two paradigms Divide-and-conquer and dynamic programming look alike on a whiteboard: both solve smaller instances of the same problem and combine the answers. The difference is not the shape of the recursion. It is whether the recursion ever reaches the **same** smaller instance twice. | Paradigm | Relationship between subproblems | Does a cache help? | | --- | --- | --- | | Divide-and-conquer | Disjoint — each input element belongs to exactly one child | No; every key is fresh | | Dynamic programming | Overlapping — one instance is reachable along many paths | Yes; that is the whole point | ## Reading the fragment The pseudocode splits a half-open range `[lo, hi)` of log records at `mid` and recurses on `[lo, mid)` and `[mid, hi)`. Those two ranges share no index, and no other path through the recursion can regenerate either of them: the top call is `(0, n)`, and every range below it is determined by the sequence of left/right turns taken to reach it. The set of keys the run produces is exactly the set of nodes of one recursion tree — about `2n - 1` of them, all distinct. So `memo contains (lo, hi)` is false every single time. The table is written `2n - 1` times and read successfully zero times. ## What overlap actually looks like Overlap appears when branching is high but the parameter space is small. Consider a recursion that, at each step, decides which of several options to take and carries the remaining state as one or two small integers — say a position and a remaining budget. The call tree is exponential in the number of steps, but the number of distinct `(position, budget)` pairs is a product of two small ranges. By pigeonhole, keys must repeat, often astronomically often. That is the signature: **an exponential call tree over a polynomial parameter space**. The practical test has three steps: 1. Write down the parameters the recursive function actually takes. 2. Bound the number of distinct tuples reachable from the top call. 3. Compare that bound to the number of recursive calls. If the parameters are a *partition* of the input — a subrange, a piece that shrinks disjointly, a half — they cannot repeat, and no cache will ever hit. If the parameters are coordinates in a small grid that many different decision sequences can land on, they repeat heavily. ## The costs a useless memo adds A cache is not free just because it is correct: - **Memory.** The plain recursion needs `O(depth)` stack. The memo holds one entry per call for the entire run. - **Time per node.** A lookup and an insert on every call, each touching a table at an essentially random location — the least friendly access pattern for a memory hierarchy. - **A new failure mode.** The key must capture every parameter the answer depends on. Omit one and the cache silently serves an answer computed under different assumptions. Nothing crashes; results are just wrong. The reason the misconception survives is that this failure is quiet. Adding a cache to a non-overlapping recursion does not break anything — the code still returns the right answer, the profile simply does not improve. Nobody gets a stack trace telling them the table never hit. ## Overlap is a property of your recursion, not only of the problem This is the part worth carrying into an interview. The **same** problem can often be recursed on in two ways. Split the input by position into disjoint halves and you get independent subproblems and no overlap. Recurse instead on "take this item or skip it, with this much budget left" and suddenly the same `(index, budget)` pair is reachable by many different take/skip sequences, and overlap is enormous. So when someone asks "is this problem dynamic programming?", the honest answer is "it depends on the recurrence I choose". Picking the formulation whose state space is small and heavily revisited *is* the skill; the table is an afterthought. ## One case that looks like an exception Keeping results across separate *invocations* — the same top-level input is queried again tomorrow and you return the stored answer — is genuine caching, and it can pay handsomely even with no overlap inside a single run. That is result caching at the boundary of the routine, not dynamic programming, and it is justified by repeated external requests rather than by the structure of the recursion. Keep the two arguments separate; they are decided by different evidence.
- How do you check for overlap without running the code?Compare two counts on paper. Bound the number of distinct parameter tuples the recursion can reach from the top call, then bound the number of calls it makes. An exponential call tree over a polynomial tuple space guarantees repeats by pigeonhole. If the parameters partition the input — disjoint ranges, halves — the counts are equal and no repeat is possible.
- Two recursive calls get ranges that share one boundary element. Is that overlap?Not by itself. Overlap is about the same parameter tuple being reached twice, not about the ranges intersecting. Sharing an element means a little duplicated work inside two distinct subproblems; the keys are still different, so a memo still never hits. Ask whether an identical key recurs, not whether the inputs touch.
- Is a cache ever worth keeping when subproblems do not overlap?Yes, but for a different reason. If the same top-level input is asked for repeatedly across separate invocations, storing the final answer pays off — that is result caching justified by external request patterns. Inside a single run of a non-overlapping recursion it remains pure overhead. Do not confuse the two arguments.
Filing every receipt in a cabinet helps only if you look receipts up again. If each one is unique and never requested twice, the cabinet is pure overhead.
saying these in an interview costs you the question
- Memoization always speeds up a recursion
- Dynamic programming is just recursion plus a cache
- Divide-and-conquer and dynamic programming are the same thing
- Every recursive call tree has overlapping subproblems
- A memo table is free, so adding one cannot hurt
- Overlap means the subranges intersect