A nightly settlement job loops once per cent of each amount; why is that not polynomial time in the input length?
answer
- measured against the file, not the money
- size of the description, not the quantity
- a value of V takes about log2(V) bits
- one extra bit doubles the trip count
- polynomial in value, exponential in length
basics
~20 sInput length is the number of symbols needed to write the instance down, not the value it denotes. An amount of value V occupies about log2(V) bits, so a loop running V times runs exponentially many steps in that length.
solid answer
~40 sComplexity is measured against `n`, the size of the instance's written description, and a monetary amount is written in a positional notation: twelve digits describe a value near a trillion. A loop that runs once per cent therefore performs about `10^d` steps on a `d`-digit amount — adding a single digit lengthens the input by roughly three bits while multiplying the work by ten. That is exponential growth in the input length even though it looks linear in the number it processes. The cost is polynomial in the **value** and exponential in the **length**, which is precisely the shape the label *pseudo-polynomial* names. The fix in review is to state what `n` is before agreeing to any bound.
code
pseudocode · 11 lines// input: one amount A, written with d decimal digits
// so the input length is about d symbols
function fee_by_counting(A):
total = 0
for k from 1 to value_of(A): // runs value_of(A) times
total = total + fee_per_cent // about 10^d iterations
return total
function fee_by_arithmetic(A):
return value_of(A) * fee_per_cent // work set by the digitsgo deeper
Remember the one substitution that matters: complexity is stated in the number of symbols the input takes to write, so a number of value one million is about twenty bits, not one million units of input.
Explain the logarithmic relationship and demonstrate it: adding one digit multiplies a magnitude-driven loop's work by ten while adding about three bits of input. Name the shape as pseudo-polynomial rather than just calling it slow.
In review, insist that a complexity claim names its n before you accept it, and be able to spot a bound stated in a capacity, a weight or an amount rather than in a count of items.
The judgment here is which magnitudes are genuinely bounded by the domain and which only look bounded by today's data. A ceiling that is a business rule can be designed around; a ceiling that is an accident of current volumes is a future incident.
## The size of an instance is the size of its description When a bound is written as a function of `n`, `n` is the number of symbols it takes to write the instance down — the bits of the file, not the quantities the file talks about. That is not a technicality; it is the whole of the definition, and every claim about tractability rests on it. A settlement file holding one amount is a short file whether that amount is four cents or four hundred billion cents, because positional notation writes a value of `V` in about `log2(V)` bits. So two different quantities live in this problem and they must not be confused: - **The value**, how large the number is. - **The length**, how many symbols are needed to write it. The length is roughly the logarithm of the value. Any cost that tracks the value therefore tracks an **exponential** function of the length: `V` is about `2^n` when `n` bits were used to write `V`. ## Value against length, with the numbers | decimal digits | largest amount | bits to write it | iterations of a per-cent loop | |---|---|---|---| | 3 | 999 | 10 | about 10^3 | | 6 | 999,999 | 20 | about 10^6 | | 9 | about 10^9 | 30 | about 10^9 | | 12 | about 10^12 | 40 | about 10^12 | Read the table down the two right-hand columns. The description grows by ten bits per three digits; the work multiplies by a thousand. Each single extra bit of input roughly **doubles** the number of loop iterations, which is the textbook signature of exponential cost in the input length. A reviewer looking only at the source sees one flat loop and calls it linear — linear in the value, which is not what the bound is asking. ## Why the source code hides it The loop body is innocent. What makes the routine exponential is that the loop's trip count is read out of the data rather than out of the data's size. Three habits catch it: 1. **Say out loud what `n` is** before accepting any complexity claim. If the answer is 'the number of records' but the routine also walks the magnitudes, the claim is incomplete. 2. **Look for a bound that mentions a value.** A bound containing an amount, a capacity, a weight, a deadline or a coordinate — as opposed to a count of items — is a bound stated in the wrong currency. 3. **Add one digit and ask what happens.** If the work multiplies while the file barely grows, the cost is driven by magnitude, not by size. ## The name for this shape An algorithm whose running time is bounded by a polynomial in the **numeric values** of its input, but not by a polynomial in the input **length**, is called **pseudo-polynomial**. The prefix is doing real work: such an algorithm is not in the polynomial-time class as the class is defined, because the class is defined over the length. The label describes the algorithm against the encoding — it is not a verdict on how hard the underlying problem is, and it is not a softer grade of polynomial. ## What this does not mean - **It does not mean the routine is useless.** Magnitude-driven algorithms are often exactly the right engineering choice, and there is a precise condition under which their cost is genuinely polynomial — when the magnitudes involved are themselves small relative to the input length. - **It does not mean every loop over data is suspect.** A loop that runs once per record is linear in a quantity that really is part of the input's size. - **It does not depend on the base.** Writing amounts in base two, ten or sixteen changes the digit count by a constant factor only, so all three give the same verdict. Only a notation whose length is proportional to the value itself changes the answer. - **It is not about the loop body's cost.** Even a body of one cheap addition leaves the routine exponential in the input length, because the trip count is what scales. ## The interview answer in one breath Complexity is measured in the bits of the instance; an amount of `d` digits is `d` symbols but about `10^d` in value; a per-cent loop therefore runs a number of steps exponential in the length of the thing it was handed, and that is what disqualifies it from polynomial time no matter how simple the loop looks.
- Does switching the amounts from decimal to base sixteen change the verdict?No. Any base of two or more writes a value of V in a number of symbols proportional to log V, so the encodings differ by a constant factor and a polynomial bound in one is a polynomial bound in the others. The verdict changes only for a notation whose length grows with the value itself rather than with its logarithm.
- The loop body is a single addition. Why does its cheapness not rescue the bound?Because the trip count, not the body, is what scales with the data. A cheap body multiplies the total by a small constant; the number of iterations is about 2^n for an n-bit amount. Constant factors cannot cancel an exponential trip count.
saying these in an interview costs you the question
- Calls the routine linear because it holds one loop.
- Treats the numeric value of an input as its size.
- Says the encoding base changes whether the bound is polynomial.
- Thinks a cheap loop body makes the total cost acceptable.
- Confuses the count of records with the magnitude of each record.