Change-making DP runs in O(n * amount) — why is that called pseudo-polynomial, and when does it hurt?

## Size versus value Complexity theory measures running time against the **length of the encoding** of the input. Give an algorithm a target amount `A`, and the input carries `A` in roughly `log A` digits. A table with one cell per amount up to `A` therefore does work proportional to `A`, which is exponential in `log A` — exponential in the size of the very thing it is reading. An algorithm whose cost is polynomial in the numeric values of its inputs but not in their encoded length is called **pseudo-polynomial**. The O(n * A) change-making and unbounded-knapsack tables are the textbook examples: `n`, the number of denominations, genuinely is part of the input size, but `A` is not. This is why you can hold two apparently contradictory facts at once: the unbounded knapsack problem is NP-hard in general, and you nonetheless solve instances of it with a fifteen-line table every day. The hardness lives in instances with enormous numbers; the table lives comfortably wherever the numbers are small. The term for that combination is *weakly* NP-hard. ## Where it actually bites Almost never in the arithmetic. The inner loop is an addition and a comparison. What goes wrong is size: - **The unit the amount is expressed in.** A day's reconciliation at a transit operator, held in the smallest currency unit, can run to tens of millions. The same amount in a coarser unit is four digits and utterly harmless. Nothing about the algorithm changed; the unit did. - **Targets that come from outside.** A budget or an amount taken straight from a request and used as an array length is an allocation whose size an untrusted caller chooses. That is a resource-exhaustion path before it is a performance problem, and it deserves a validated ceiling on the input, not a bigger machine. - **Memory bandwidth, not instructions.** A table of tens of millions of cells is scanned once per denomination. Each sweep streams the entire array past the cache. The loop is trivially fast per cell and completely bound by memory traffic. ## What to do about it **Rescale by the greatest common divisor.** If every denomination shares a common factor `g`, then only multiples of `g` are reachable at all. Check the target: if it is not a multiple of `g`, the answer is immediately "unreachable" with no table at all. If it is, divide every denomination and the target by `g` and solve the smaller instance — the coin counts are unchanged, because you rescaled the units, not the selection. A denomination set whose values are all multiples of 25 shrinks the table twenty-five-fold for free. **Bound the target and precompute.** In most real systems the denomination set is fixed and the largest amount ever served is known: the highest fare, the largest bundle. Fill the table once at startup up to that bound and answer every subsequent query with an array read. This converts a per-request O(n * A) cost into a one-time cost plus O(1) lookups, and it makes the memory footprint a startup decision you can measure rather than a per-request surprise. **Reformulate when the target dwarfs the denominations.** When the smallest denomination is small but the target is astronomically larger, there is a known refinement that works over residue classes modulo the smallest denomination rather than over every amount, reducing the table from the target's magnitude to that smallest denomination's magnitude. It is a specialist tool and rarely needed, but it is the right answer to "the target is a billion and I have six denominations". ## The claim to state precisely Be careful with the direction of the argument in an interview. O(n * A) is not "slow" — it is linear in a quantity that merely happens not to be the input size. And NP-hardness is not a verdict on your instance. The honest senior answer is numeric: here is the largest target this service can be handed, here is the unit it is in, here is the resulting allocation, and here is why that is or is not acceptable on the fleet this runs on. A candidate who says "it is exponential, so we cannot use it" has drawn the wrong conclusion just as surely as one who says "O(n * A) is polynomial, so it scales". ## A review checklist When this table shows up in a change under review, three questions settle it. What is the maximum value the target can take, and is it validated? What unit is it expressed in, and could a coarser unit or a gcd rescale shrink it? Is the table built per request or once? Those three answers decide whether the code is fine forever or an outage waiting for a large input.