Card 08/ 10
Costing a Dynamic Programme: States Times Work per State
Count the states, multiply by the work each takes, and check whether a number in the input is a value or a length.
The running time of a dynamic programme is the number of states multiplied by the work done to fill each one, and the space is the number of states kept. This card shows how to read both off a recurrence, and why a cost that looks polynomial can still be slow when one of its numbers is a value rather than a size.
The stall problem has one state per stall, and each state takes a maximum of two numbers, so it costs O(n) time and O(n) space, or O(1) space once it is rolled. Every dynamic programme is costed the same way: say what one state is, count how many there are, and count the steps the recurrence takes for one of them. The table below does that for the problems in this subject.
| Problem | States | Work per state | Time | Polynomial in the input's length |
|---|---|---|---|---|
| No neighbours, n stalls | n | O(1), a maximum of two | O(n) | Yes |
| Door code, n digits | n | O(1), at most two sums | O(n) | Yes |
| Longest common subsequence, lengths m and n | m × n | O(1) | O(m × n) | Yes |
| Fewest coins, k coin values, amount A | A | O(k), one try per coin | O(A × k) | No: A is a value |
| 0/1 knapsack, n items, capacity W | n × W | O(1), take or leave | O(n × W) | No: W is a value |
The last column is the trap. An algorithm is polynomial when its time grows as a power of the input's length, the number of digits or bits it takes to write the input down. The stalls, the digits and the two strings are as long as the counts in their costs, so those costs are polynomial. The capacity W is different: it is one number, and writing it takes only about log₂ W bits. Doubling the number of digits in W squares W itself, so O(n × W) grows exponentially in the length of W. A cost like that is called pseudo-polynomial: polynomial in the value of a number, exponential in its length.
The difference shows at real sizes. A run sized a knapsack table for 100 items and a capacity of W = 10⁹: one row per item and one column for every capacity from 0 to W gives 100 × (10⁹ + 1) = 100,000,000,100 entries, yet W takes only 30 bits to write. At one byte an entry that is about 100 GB, for an input a few hundred bytes long.
So cost a dynamic programme before writing it. When every factor in states times work is a length, it scales with the input. When a factor is a value, such as a capacity, an amount or a target sum, check its largest realistic size: small values, such as amounts in pence up to a few thousand, make the table cheap, and large ones need a different state, a different algorithm, or an approximation.
← → move through sections and cards