A subset-sum DP runs in O(n*W) with amounts up to 10^9 cents — why isn't that polynomial time?
answer
- input size is measured in bits
- how many digits does the target need?
- compare W against log W
- polynomial in value, not in length
- pseudo-polynomial, and why the problem stays NP-hard
basics
~20 sComplexity is measured against input length in bits, and the bound W needs only about log W bits to write down. O(n*W) is therefore exponential in the encoding length — pseudo-polynomial, which is why subset-sum stays NP-hard despite the table.
solid answer
~50 sPolynomial time means polynomial in the *length of the encoded input*, and a target of one billion cents is written in about 30 bits, not a billion. So `O(n*W)` is `O(n * 2^(bits of W))` — exponential in the size of the number, even though it looks linear in the number's value. That is what pseudo-polynomial means, and it is why an efficient-looking table does not settle the complexity class of subset-sum. Practically, splitting payments with cent precision gives a table of billions of columns: infeasible in both time and memory. The escapes are all reformulations, not micro-optimizations — bound the target by something polynomial in `n`, coarsen the unit and accept an approximation with a stated error bound, or for small item counts use a subset-splitting search whose cost depends on `n` alone rather than on the magnitudes.
go deeper
Be ready to state the bound itself and to notice that one of its factors is an amount read from the input rather than a count of items.
Explain that complexity is measured against the encoded input length, so a factor proportional to a value is exponential in that value's bit count — the definition of pseudo-polynomial.
Diagnose the shape in a real design: say why cent precision makes the table infeasible, which regime the instance is in, and which reformulation you would reach for and what it costs in accuracy.
Own the exact-versus-approximate decision under real constraints — memory ceilings, precision the business actually requires, and whether a solver or a coarser unit with a documented error bound is the responsible answer.
## Complexity is measured in bits, not in values The formal definition of polynomial time is: running time bounded by a polynomial in the **length of the input encoding**. An instance here consists of `n` amounts and a target `W`. Writing `W` down takes about `log2(W)` bits — a target of a billion cents fits in 30 bits. So an algorithm whose running time is proportional to `W` is proportional to `2^(number of bits of W)`. Relative to the input length, that is exponential. The `O(n*W)` bound is real and correct; it is just measured against the wrong yardstick when someone calls it polynomial. Algorithms with this shape have a name: **pseudo-polynomial** — polynomial in the numeric *value* of the input, exponential in its *size*. ## Why this matters and is not pedantry Subset-sum and the 0/1 knapsack family are NP-hard. If an `O(n*W)` table were polynomial time, that would be a proof of P = NP. The pseudo-polynomial distinction is precisely what keeps the tabulation and the hardness result consistent with each other. In an interview, a candidate who says "knapsack is NP-hard but there's an O(nW) DP" without reconciling the two is going to be probed; the reconciliation is this paragraph. There is also a sharper version of the concept. A problem is **strongly NP-hard** if it stays NP-hard even when all numbers in the instance are bounded by a polynomial in the instance size — such problems admit no pseudo-polynomial algorithm at all unless P = NP. Subset-sum is *weakly* NP-hard, which is exactly why the value-indexed table exists for it. ## The practical face of it Split a payment across contributors so a subset of contributions sums exactly to a bill, with amounts held in cents and bills up to about 10^9 cents. The table has one column per reachable total: on the order of 10^9 columns per row. Even with a compressed single live row of bits, that is a data structure sized by the *currency precision*, not by how many people are splitting the bill. Adding one contributor is cheap; changing the unit from dollars to cents multiplies the table by one hundred. That asymmetry — cost driven by magnitudes rather than by item count — is the fingerprint of a pseudo-polynomial algorithm in the wild, and recognizing it early is worth more than any constant-factor tuning. ## What actually escapes it - **A genuinely polynomial bound on the target.** If the problem guarantees the target is at most some polynomial in `n` (say totals bounded by a small multiple of the item count), then `n*W` really is polynomial in the input size, and the pseudo-polynomial objection evaporates. Always check whether your `W` is a small structural quantity or an arbitrary magnitude. - **Coarsening the unit, accepting approximation.** Rescaling amounts to a coarser unit shrinks `W` proportionally and shrinks time and memory with it — at the price of an answer that is only correct within the rounding. This is the seed of the classic approximation schemes for the optimization version: choose the scaling to bound the relative error, and trade accuracy for a running time that is polynomial in `n` and in the reciprocal of the error tolerance. - **Making the cost depend on item count instead.** When `n` is small but magnitudes are huge, an approach that splits the items into halves, enumerates the achievable sums of each half, and matches them costs roughly `2^(n/2)` — infeasible for large `n`, but entirely insensitive to how big the amounts are. Which regime you are in decides which algorithm is even eligible. - **Handing it to a solver.** For real business instances, a specialized integer-programming or constraint solver often beats any hand-rolled table, because it prunes rather than enumerating a magnitude-sized space. ## The reasoning habit to take away Whenever a complexity contains a bound, a capacity, a target sum, a coordinate range or a time horizon as a *multiplicative factor*, ask one question before quoting it: **is that quantity a count of input items, or a numeric value read from the input?** Counts are input size. Values are exponentially compressible into bits. Two bounds that look identical on the board — `O(n*m)` where `m` is a second list's length, versus `O(n*W)` where `W` is a target amount — belong to different complexity worlds, and only one of them is polynomial. Interviewers use this exact confusion to separate candidates who recite bounds from candidates who understand them.
- What would make the very same O(n*W) bound genuinely polynomial?A guarantee that `W` is bounded by a polynomial in `n` — for instance if totals cannot exceed a small multiple of the item count. Then `W` is effectively a count rather than an arbitrary magnitude, and `n*W` is polynomial in the input length. The bound did not change; the promise about the instance did.
- The team proposes rescaling cents to whole dollars to shrink the table 100-fold. What do you tell them?Time and memory fall by the same factor, and the answer becomes approximate: sums are now correct only to the rounding, so exact-match requirements break. If approximate is acceptable, choose the scale from a stated error target rather than from convenience, document the guarantee, and add a check for cases where the exact answer is legally or financially required.
- n is only 40 but amounts are enormous. Does the table still apply?Poorly — its cost is driven by magnitude, which is the bad regime here. With a small item count, splitting the items into halves and matching achievable sums between them costs on the order of `2^(n/2)` and is completely insensitive to how large the amounts are. Which regime you are in decides which algorithm is eligible.
- Do all NP-hard problems have a pseudo-polynomial algorithm like this one?No. Strongly NP-hard problems remain hard even when every number in the instance is bounded by a polynomial in the instance size, so no pseudo-polynomial algorithm exists for them unless P equals NP. Subset-sum is weakly NP-hard, which is precisely why a value-indexed table exists for it at all.
A phone number is quick to write down yet names one of ten billion possibilities. An algorithm that walks every possibility is cheap in the number of digits you were handed only in appearance — it pays for the possibilities, not for the digits.
saying these in an interview costs you the question
- Calls O(n*W) polynomial because both factors look linear
- Confuses a numeric value with an input count
- Claims the table disproves the problem's NP-hardness
- Thinks the issue is only large constant factors
- Assumes every NP-hard problem has such a table