Why does memoizing an exponential recursion change its time complexity, and to what?
answer
- what does the naive recursion repeat?
- count distinct subproblems, not call paths
- each state computed once, then looked up
- total equals states times work per state
- no repeats means no savings
basics
~20 sMemoization computes each distinct subproblem once and reuses the stored result, so cost drops from the number of call paths to (number of distinct states) times (work per transition). It only helps when subproblems actually repeat.
solid answer
~50 sThe naive recursion is expensive because the same subproblem is re-derived along many different call paths. Take a dependency resolver that, for 40 packages, decides include-or-skip at each step: the raw recursion tree has on the order of `2^40` paths. Add a cache keyed by the subproblem's state and each distinct state is computed once and afterwards returned by lookup, so the total becomes (number of reachable distinct states) x (cost of one transition), plus the cost of the lookups themselves. If the state is just "which package index am I at", that is 40 states and the run is trivial; if the state is "index plus the exact set already chosen", the states are still exponential and the cache saves nothing. So the honest answer always names the state space — never just "memoization makes it fast".
go deeper
Be ready to say that a cache turns repeated subproblem calls into lookups, and that you count distinct subproblems rather than branches of the recursion tree.
Explain the accounting out loud: total time is the number of reachable states times the work one transition does, and state what a single state means in the problem at hand.
Show that you verify subproblems genuinely overlap before promising a speedup, and that you size the cache against real limits — entry count, key cost, and the memory it holds at production input sizes.
Own the call on whether an exact cached solution is worth its memory at scale, and when a bounded approximation or a different formulation beats a cache that will never fit in the budget you have.
## The two numbers you must say out loud A memoized recursion's running time is, to a very good first approximation: **time = (number of distinct states actually reached) x (cost of computing one state from its dependencies)** plus the cost of the cache operations themselves. Almost every wrong answer in this area comes from quoting only one of those two factors, or from quoting neither and saying "it becomes linear". ## Why the naive version is exponential in the first place Recursion becomes exponential when the recursion *tree* is much bigger than the set of *distinct* arguments in it. Consider resolving a dependency set: you walk a list of 40 candidate packages and at each one decide to include it or skip it, recursing on the rest. The tree of decisions has two children per level and 40 levels, so it contains on the order of `2^40` root-to-leaf paths — about a trillion. That number counts *paths*, not *problems*. Many of those paths arrive at the very same question: "what is the best I can do from package 17 onward, given I have this much budget left?" The exponential blow-up is repeated work, not necessary work. This is the *overlapping subproblems* property. It is a property of the problem plus the chosen state encoding — not something memoization creates. ## What the cache changes A memo is a table keyed by the state. The first time a state is requested you compute it and store it; every later request is a lookup. Charge the work with aggregate accounting: over the whole run, exactly one "compute" happens per distinct reached state, and every other call is a lookup that returns immediately. So: - Number of computes = number of distinct reached states, call it `S`. - Work per compute = the transition cost `T` — the number of dependencies it combines, plus whatever it does per dependency. - Number of lookups = at most `S x (branching factor)`, because every compute issues at most that many child requests; each lookup is expected constant time for an array-indexed table and expected constant for a keyed cache with a good hash. Total: `O(S x T)`. For the 40-package resolver with state "(index, remaining budget)" and an O(1) transition, that is `41 x (budget+1)` computes — an utterly different animal from `2^40`, and the sentence an interviewer wants is exactly that pair of numbers stated side by side. ## The trap: "memoization makes it O(n)" The most common wrong answer names the *problem input size* instead of the *state space*. Two failure shapes: 1. **Multi-dimensional state.** If the state is a pair (position, remaining capacity), `S` is the product of the two ranges, not the length of the input. Saying "O(n)" silently drops a whole dimension. 2. **Non-constant transition.** If computing one state scans all earlier positions, `T` is itself `O(n)` and the product is a factor of `n` bigger than the table size. Counting cache entries is not counting time. A good habit: before quoting a complexity, say the state tuple aloud, count how many values each component can take, multiply, then separately describe what one transition does. ## When memoization does not help at all If no two call paths ever reach the same state, the cache is written to and never read; the asymptotic time is unchanged and you have added memory and hashing overhead for nothing. Enumerating every distinct ordering of a set behaves this way — each path ends somewhere unique. This is why "has overlapping subproblems" is a precondition you check, not a wish. Likewise, if the state must encode an arbitrary subset of the items to be correct, the state space is exponential and memoization gives you an exponential-space algorithm that is still exponential in time — occasionally a real win in practice on small inputs, but never a change of complexity class. ## Space is part of the answer The cache holds up to `S` entries, so the space is `O(S)` for the table plus the recursion stack, whose depth is part of the algorithm's space too. "It runs fast now" is only half a report; interviewers routinely follow up with "and how much memory does that cache hold at your real input sizes?" — a cache with billions of entries is not a solution. ## The one-sentence summary Memoization does not make things fast; it removes *repetition*, converting call-path counting into state counting. What is left is states times transition cost, and you must be able to name both.
- Your memo ends up with 40 entries. Does that make the algorithm O(40)?Only if one entry costs constant time to compute. The running time is entries times transition cost, so a state whose transition scans a list of length m costs `40 x m`. And check the key: if the real state is a pair, the entry count is the product of both ranges, not the length of one input.
- When does adding a memo leave the asymptotic time unchanged?When distinct call paths never collide on the same state, so every cache write is followed by no read. Enumerating all distinct orderings of a set behaves like that. You pay memory and key-hashing cost and get nothing back, which is why you verify overlapping subproblems before promising a speedup.
- The recursion is memoized but still too slow. What do you look at first?The state definition. An over-specified state — carrying data the recurrence does not actually need — multiplies the state count and destroys the overlap that makes caching work. Second, the transition: a per-state scan may be replaceable with a running aggregate. Third, whether the cache key itself is expensive to build or compare.
Working out a hard sum once and writing it on a sticky note: the total effort is how many different sticky notes you end up needing, times what each one costs to work out — not how many times someone asks you for one.
saying these in an interview costs you the question
- Says memoization always makes it linear
- Quotes a complexity without naming the state space
- Counts cache entries but ignores per-state work
- Assumes subproblems overlap without checking
- Treats the cache's memory as free
- Counts nodes of the recursion tree as distinct states