When does memoizing a pricing calculation stop paying for the memory it consumes?

## The trade, stated as two numbers Memoization is the purest time-space tradeoff there is: keep the result of a computation so the next request for the same input is a lookup instead of a recomputation. Whether it is worth doing reduces to comparing two quantities: - **What it costs:** `distinct keys reached × bytes per entry`, held for as long as the table lives. - **What it buys:** `(calls − distinct keys) × cost of one recomputation`, minus the lookup overhead paid on every call. Both halves get estimated badly in interviews, in opposite directions. ## Costing the table: distinct keys, not calls The table's size is bounded by the number of *distinct* keys the run actually touches — never by the number of calls, and only loosely by the theoretical key space. For a pricing calculator keyed by `(product, region)`, the ceiling is catalogue size × region count. A modest-sounding 50,000 products across 200 regions is 10 million pairs; at roughly 50 bytes per stored entry (the two key fields, the price, and the per-entry overhead any keyed structure carries) that is around half a gigabyte for a cache nobody put on a capacity plan. Two observations follow. First, the *reachable* key count is what matters, and it is often far below the theoretical product. If ninety percent of revenue comes from two thousand products in six regions, the working set is twelve thousand entries and the table is trivial — but only if entries for the long tail are never created, or are evicted when they are. Second, bytes per entry is not the size of the value. A keyed lookup structure stores the key too, plus per-slot bookkeeping, plus empty slots kept deliberately so lookups stay fast. Estimating a memo as "8 bytes per price" is off by roughly an order of magnitude, and that error is exactly the size of the gap between "fits comfortably" and "does not fit". ## Costing the benefit: the hit rate is the whole story A memo entry that is written once and never read is pure loss — memory spent, plus the write, plus the lookup miss that preceded it. So the question to ask about any memo is: *what makes a key repeat?* - A **sweep** that visits every key exactly once (repricing the whole catalogue overnight) has a hit rate near zero. Memoizing it is strictly worse than not. - A **skewed live workload** where a small set of popular pairs is requested constantly has a hit rate near one, and the memo is close to free money. - A **recursive decomposition** where subproblems genuinely overlap is the classic win, and there the memo does not merely save time — it collapses an exponential number of repeated subproblems into a polynomial number of distinct ones. When memoization changes the complexity class like that, it stops being an optimization you weigh and becomes the algorithm. That last case is the important asymmetry. If the memo turns exponential into polynomial, you keep it even when the table is large. If it merely turns 100 calls into 10 calls of something that takes a microsecond, the table has to be nearly free to be worth its memory. ## Bounding, invalidating, and the honest failure modes An unbounded memo inside a long-lived process is a memory leak with a friendly name: it only grows, its growth is driven by traffic patterns nobody controls, and it fails at the worst moment — under peak load, when the key space widens. Two disciplines contain it. **Bound the table** to a fixed entry count and let it discard entries under a replacement policy, accepting a lower hit rate for a hard memory ceiling. And **decide when an entry is wrong**, because a memo assumes the underlying computation is a pure function of its key; a price that depends on a promotions table that changed at noon has a correctness problem, not a memory one, and stale-entry bugs are far more expensive than the recomputation the memo saved. A useful diagnostic when someone proposes a memo: ask for the expected number of distinct keys per hour and the expected number of calls per hour. If those two numbers are close, the memo will not pay. If the first is small and the second is large, it will. If nobody can estimate either, the right first step is to measure the recomputation cost and the key distribution, not to ship the table. ## The interview-shaped summary "Memory is distinct keys times bytes per entry — for this key space that's roughly N entries and X hundred megabytes. The benefit is the repeat rate; in a one-pass sweep it is zero, in a skewed live workload it is high. I'd memoize in the second case with a bounded table, and skip it in the first."