For an n x W DP table compressed to a single row, what are the space and time complexities?

## Two separate ledgers A dynamic program has a time ledger and a space ledger, and they are computed differently: - **Time** = number of states x transition cost. It counts every cell that is *computed*. - **Space** = number of cells that must be *alive simultaneously*, plus any auxiliary structures, plus the recursion stack if the formulation is recursive. Row compression touches only the second ledger. Every cell of the conceptual `n x W` table is still evaluated exactly once, so `O(n*W)` time stands. The saving is that you stop *keeping* the finished rows. ## Why one row suffices, and when it does not Compression is licensed by the dependency pattern, not by wishing. If the recurrence for row `i` reads only cells in row `i-1` (and possibly earlier cells of row `i` itself), then once row `i` is complete, row `i-1` is dead and its storage can be reused. Space becomes one row: `O(W)`. If the recurrence reads rows `i-1` and `i-2`, you keep two rows — still `O(W)`, just a bigger constant. If it can read *any* earlier row, nothing may be discarded and the space stays `O(n*W)`. The rule is: **live space is the size of the dependency frontier**, and the frontier is whatever the recurrence can still reach backwards. ## The claims that go wrong **"Compression makes it faster."** No. The same cells are computed in the same order. There is a real constant-factor effect — a smaller working set is friendlier to memory caches and to allocation — but it is a constant, and describing it as a complexity improvement is a mis-statement of what big-O measures. **"Now it is O(1) space."** Only if the row itself is constant size, which it is not: it is `O(W)`. A single row of length `W` is a linear structure, and calling it constant confuses "a fixed number of rows" with "a fixed number of cells". **"The stack does not count."** Recursion depth is space. A top-down formulation with a memo of `S` entries and worst-case depth `d` uses `O(S + d)` space; when `d` is proportional to the input, that term can dominate a compressed table and is the reason a deep recursion can exhaust memory even when the cache is modest. **"The memo is not part of my algorithm's space."** It is. Anything the algorithm allocates and needs for correctness is counted, whether it lives on a stack or elsewhere. ## Reporting space honestly A complete space statement names its parts: the live table cells, plus auxiliary arrays (prefix sums, precomputed transition costs), plus the recursion stack when applicable, plus the output if it is larger than constant size. Interviewers ask about space far less often than time — which is exactly why a candidate who volunteers a precise, decomposed space bound stands out. Say something like: "one live row of `W` entries, plus a precomputed cost array of `n` entries, plus constant scratch — so `O(n + W)`." ## The thing compression costs you Discarding rows discards the record of *how* each cell was reached. If the caller needs the optimal value, that is fine. If the caller needs the actual selection that achieved it, the discarded rows were the evidence, and recovering the choices needs either the full `O(n*W)` table kept or a different reconstruction strategy — a real space-versus-capability tradeoff, and a question to ask the caller before optimizing. ## The scale caveat that outranks all of this `O(W)` is a promise about how the footprint *grows*, not that it is small. If `W` is a numeric bound like a total in the smallest currency unit, a single row can still be billions of entries. Compression divides the footprint by `n`; it does not rescue a table whose width is set by a large numeric value rather than by the count of input items. Recognize that shape early: the fix there is a different formulation or a coarser unit, not a rolling row. ## Summary Time is what you compute; space is what you keep alive at once. Compression changes only the second, from `O(n*W)` to `O(W)` when the frontier is one row — and your space report is incomplete until it also accounts for the recursion stack and any auxiliary arrays.