Computation is about exploring Search Spaces

Computation is often best understood as exploring a search space. An algorithm is not expensive because one step is mysterious. It is expensive because there may be many states to visit.

Pseudo-dynamic Dynamic Programming

A table lookup such as $T[i,s]$ looks constant-time. The hidden cost is the size of the table that must be filled. For knapsack-like dynamic programming, the search space is

$$\mathcal{S}=\{0,\dots ,n\}\times \{0,\dots ,S\},$$

with size $|\mathcal{S}|=(n+1)(S+1)$. One lookup is cheap, but filling the table means exploring this whole search space.

This is why pseudo-polynomial dynamic programming can be deceptive. If $S$ is stored in binary, then $S$ may be exponential in its bit-length. The table notation hides that a compact input field has been expanded into many states.

The same perspective also explains why dynamic programming is powerful. It avoids exploring every history separately. Many histories can collapse into one state, and the algorithm stores only the best value for that state. Pseudo-Polynomial Dynamic Programming is about Compression.

Chiselling Complexity

So computation is about the shape and size of the search space being explored. Complexity asks how large that explored space is relative to the encoded input size.