Knapsack's Hidden Exponential: One Zero, Ten Times Slower
Digits in capacity W
4 digits
W = 10^d
10,000
n = 10 items (fixed)
Grid cells = n × W = n × 10^d
Linear Scale
n × W vs W — looks polynomial
Log Scale (digits d)
n × 10^d vs d — each step = ×10
Digits (d)
4
Grid cells (n × W)
100,000
Time @ 10^9 ops/s
0.0001 s
Runtime = O(n × W) = O(n × 10^d) — exponential in input length d, not d × 10.
Adding one digit to W multiplies the grid by 10. The algorithm is pseudo-polynomial: polynomial in the value of W, but exponential in its bit-length.