When does the O(nW) 0/1 knapsack table lose to exponential subset search, and how do you decide?
answer
- which parameter is actually large here
- a capacity is a magnitude, not a count
- thirty items is a small exponent
- multiply the numbers before choosing
- count the bytes one row would need
basics
~20 sThe table loses when the capacity limit is enormous and the item count is not: 30 items and a billion-unit limit cost tens of billions of updates and gigabytes, while halved subset enumeration takes about a million operations.
solid answer
~50 sThe O(nW) bound is polynomial in the item count and in the capacity **number**, but the capacity is a magnitude, not a count of inputs — doubling the units you measure weight in doubles the table for free. So the decision is arithmetic, not asymptotic. Multiply: 30 items and a limit of one billion is roughly 3 × 10^10 cell updates and a row of a billion cells; splitting the items into two halves and enumerating each half's 2^15 subset sums, then matching them, is around a million operations. Flip the numbers — 5,000 items and a limit of 10,000 — and the table wins outright at 5 × 10^7 updates and trivial memory. I decide on the real input distribution, and I check first whether dividing all weights and the limit by their common factor shrinks the table enough to keep the version the whole team can review.
go deeper
Know that a knapsack table's size is driven by the capacity limit, not only by how many items there are, so a huge limit means a huge table.
Be able to multiply before claiming efficiency: item count times capacity for the updates, one cell per capacity unit for the memory, evaluated on the actual numbers.
Estimate both candidates against the real input distribution and choose with figures, including the option of dividing every weight and the limit by their common factor first.
Own the tradeoff between an approach the whole team can review and a faster one needing its own oracle, decided under the service's memory ceiling and latency budget, with the crossing point written down.
## The claim under test "The dynamic program is O(nW) and brute force is O(2^n), so the dynamic program always wins." It is the most common confident wrong answer about this problem, and it is wrong because the two expressions are measured in different currencies. `n` is a count of inputs. `W` is a **number that appears in the input**. Writing a capacity of one billion takes about 30 digits' worth of storage, but it makes the table a billion columns wide. Change the units from kilograms to grams and the input is barely longer while the table grows a thousandfold. An algorithm whose cost tracks a value's magnitude rather than the input's length can be arbitrarily expensive on a tiny input. ## Do the arithmetic, on both candidates **Capacity-indexed table.** `n = 30`, `W = 10^9`. Time: 3 × 10^10 cell updates — tens of seconds at best, single-threaded, and that is with a perfectly cache-friendly sweep, which a billion-cell row is not. Memory: one cell per capacity unit. Even one byte per cell is a gigabyte; a real value cell of four or eight bytes is four to eight. Per request, in a shared service, that is disqualifying before the latency argument starts. **Enumerating in halves.** Split the 30 items into two groups of 15. Enumerate each group's 2^15 = 32,768 subset totals. Sort one side's totals and keep, for each weight prefix, the best value seen so far; then for each total on the other side, binary-search the largest complementary weight that still fits. That is on the order of 10^6 operations and a few megabytes — effectively instant. It is exponential in `n`, and at `n = 30` that exponential is small. The crossing point is not a constant; it is where `n · W` stops being smaller than roughly `2^(n/2) · n`. Both sides of that comparison come from your workload, not from a textbook. ## The decision framework 1. **Measure the real distribution, not the specification.** Specs say "weights up to 10^9"; traffic often says "almost always under 10^4, with a long tail". Those imply opposite choices, and only one of them is written down. 2. **Try to shrink W before abandoning the table.** If every weight and the limit share a common factor, divide them all by it — the problem is unchanged and the table shrinks proportionally. Weights in whole units disguised as cents are the usual finding. 3. **Ask whether the answer must be exact.** If a bounded error is acceptable, rounding weights to a coarser unit shrinks the table by that factor at the cost of a stated, provable error bound. That is a product decision with a named tradeoff, not a silent code change — it needs an owner outside engineering. 4. **Count bytes per request, not just operations.** A shared service with a memory ceiling per request rules out capacity-sized arrays regardless of how fast they would be. 5. **Price the maintenance.** The flattened table is a handful of lines any reviewer can verify. Halved enumeration needs careful prefix-maximum reasoning, and its bugs are silent wrong answers. If you ship it, ship the slow exhaustive version alongside it as a differential-test oracle, and keep the simple table on the paths where it is affordable. 6. **Handle the mixed case explicitly.** Choosing per request by the observed `n` and `W` is legitimate, but two code paths means twice the test surface and a documented threshold that someone must re-measure when traffic shifts. ## When the table is clearly right Many items, small limit. 5,000 items with a capacity of 10,000 is 5 × 10^7 updates and a 10,001-cell row — a few milliseconds and a few tens of kilobytes, while any subset enumeration over 5,000 items is not merely slow but physically impossible. This is the common case, which is why the table is taught first; it is just not the universal case. ## The judgment being tested Nobody is asking you to recite two complexity expressions. They are asking whether you will multiply the numbers before committing a service to an algorithm, whether you can name the constraint that actually binds — memory ceiling, latency budget, or the team's ability to maintain the clever version — and whether you would accept an asymptotically worse choice when the constraint says so. The strongest answer names the crossing point in the workload's own units and says what would make you revisit it.
- The limit is huge but every weight is a round number. What do you try before giving up on the table?Divide every weight and the limit by their greatest common divisor. The problem is identical and the table shrinks by that factor — weights recorded in cents that are always whole units are the classic finding. If the answer may be approximate, rounding weights to a coarser unit shrinks it further for a stated error bound, but that is a product decision with an owner, not a quiet code change.
- Five thousand items with a capacity of ten thousand — which approach do you pick?The table, without hesitation: about 5 × 10^7 cell updates and a row of ten thousand cells, so milliseconds and kilobytes. Any subset enumeration over five thousand items is not slow but impossible, and halving the exponent does not help at that scale. This is the case the table was designed for, and it is the common one.
- How would you justify shipping the more complex halved enumeration to your team?With numbers and a safety net. Show the measured input distribution and the operation counts for both, keep the exhaustive enumeration as a differential-test oracle on small inputs, and leave the simple table on the traffic where it is affordable. Document the crossing point in the workload's own units and name the signal that would trigger re-measuring it.
saying these in an interview costs you the question
- Says polynomial always beats exponential regardless of the numbers
- Treats the capacity limit as if it were the item count
- Quotes O(nW) without ever multiplying the actual values
- Ignores the memory a capacity-sized row costs per request
- Ships the clever algorithm with no correctness oracle