Why is a DP that fills an n x K table with an inner scan over earlier positions not O(n*K)?

middlemust knowfreq 72%

answer

table size is only half the story
what happens inside one cell?
count states, then count work per state
the inner scan multiplies the total
n*K cells times an O(n) scan

basics

~20 s

DP time is (number of states) times (cost of one transition), not table size alone. With nK cells and an inner scan of up to n predecessors, the cost is O(n^2K); counting cells hides the inner loop.

solid answer

~50 s

The table tells you how many states there are, not how much each one costs. Here the states are the n x K pairs (version index, snapshots used), so S = n*K, but computing one cell scans every earlier version as a possible previous snapshot point, so the transition cost T is O(n). Time is S x T = O(n^2 * K); space is O(n*K) for the table. A cleaner way to say it: DP time equals the number of edges in the state dependency graph, because every edge is relaxed once. When transitions differ in cost across states, sum instead of multiplying — the product S x T is really an upper bound using the worst transition. The takeaway an interviewer listens for is that you counted two things separately and multiplied them, rather than reading a complexity off the table dimensions.

The table tells you how many states there are, not how much each one costs. Here the states are the `n x K` pairs (version index, snapshots used), so `S = n*K`, but computing one cell scans every earlier version as a possible previous snapshot point, so the transition cost `T` is `O(n)`. Time is `S x T = O(n^2 * K)`; space is `O(n*K)` for the table. A cleaner way to say it: DP time equals the number of edges in the state dependency graph, because every edge is relaxed once. When transitions differ in cost across states, sum instead of multiplying — the product `S x T` is really an upper bound using the worst transition. The takeaway an interviewer listens for is that you counted two things separately and multiplied them, rather than reading a complexity off the table dimensions.

code

pseudocode · 11 lines

pseudocode

# dp[i][k] = min cost to cover versions 1..i using exactly k snapshots
# replayCost(a, b) is precomputed and costs O(1)
# every dp entry other than dp[0][0] starts at INF
dp[0][0] = 0
for i in 1..n
    for k in 1..K
        for j in 0..i-1
            cand = dp[j][k-1] + replayCost(j+1, i)
            if cand < dp[i][k]
                dp[i][k] = cand
answer = min over k in 1..K of dp[n][k]

go deeper

for a junior

Be ready to point at the loops: the outer ones count states, the inner one is extra work per state, and both go into the final number.

for a middle

Explain the product form out loud — states times transition cost — and give both numbers separately for the recurrence in front of you, including what a helper inside the transition costs.

for a senior

Turn the count into a capacity statement: at the real n and K, how many operations is that, and does the transition-cost lever or the state-space lever get you under the latency budget first?

for a principal

Own whether a cubic-ish exact formulation is acceptable for the workload's growth curve, or whether the team should invest in a reformulation, and be able to justify that call in engineering time as well as cycles.

The accounting rule

For any dynamic program:

time = sum over states of (cost of that state's transition)

and when transitions are roughly uniform this collapses to the product everyone quotes:

time = (number of states) x (transition cost)

The number of states is the size of the table you fill. The transition cost is the work done inside one cell: how many predecessor states it combines, and what it does per predecessor. Reading a complexity off the table's dimensions alone silently assumes the transition is O(1), which is often false.

The worked example

The fragment attached to this question places snapshots in a versioned document. State is (i, k): the first i versions are covered using exactly k snapshots. There are n*K such states. The recurrence chooses where the last snapshot block began, so it scans every j from 0 to i-1, reading dp[j][k-1] and adding a precomputed replay cost. That inner loop is the transition, and it runs up to n times.

So the count is: n*K states, O(n) per state, total O(n^2 * K) time, O(n*K) space. With n = 5000 versions and K = 20 snapshots that is on the order of 5*10^8 basic operations — an entirely different planning conversation from the 10^5 that O(n*K) would suggest. Getting this factor wrong is how a design passes a whiteboard and dies in production.

The edge-counting view, which is more robust

Every DP defines a directed acyclic graph: one node per state, one edge per dependency of the recurrence. Filling the table relaxes each edge exactly once. Therefore:

time = O(number of states + number of dependency edges), assuming each edge costs constant work.

This phrasing survives cases where the product form misleads. If most states have a two-way transition but a handful scan the whole input, the product S x T_max overstates the truth, while summing the per-state costs (equivalently, counting edges) gives the honest bound. It also handles ragged tables — where the reachable range of one dimension depends on another — that the rectangle-shaped product overcounts.

Where candidates go wrong

Quoting table size as time. "The table is n by K, so it's O(nK)" — correct only when a cell is computed in constant time from a fixed number of neighbours.
Quoting time as space. Time and space are different counts here: O(n^2 K) versus O(nK). They coincide only when transitions are O(1).
Forgetting work hidden behind a helper. The fragment's replay cost is a precomputed constant-time lookup; if it were computed on demand by walking a range, the transition would gain another factor of n and the total would be O(n^3 K). Always ask what a helper costs before charging it as free.
Charging the transition per cell when it is per edge. If a cell's scan is bounded by its own index rather than by n, the true sum is K times the sum of i over all i, which is O(n^2 K / 2) — the same class, but the reasoning is the sum, not the rectangle.
Ignoring that the state itself may be expensive to key or copy. If a state is a set or a string rather than a small tuple, hashing and comparing it is a per-operation cost that multiplies into everything.

Reducing the transition, not the table

Once you see time as a product, two independent levers appear. Shrink the state space, or shrink the transition. The second is often the easier win: an inner scan that is picking a minimum over a sliding window of predecessors can frequently be replaced by a running aggregate carried along the loop, taking the transition from O(n) to O(1) and the total from O(n^2 K) to O(n K) with the same table. That is a complexity improvement obtained without changing what a state means, and interviewers like hearing it named as a separate lever from state reduction.

How to present this in an interview

Say it in three beats: "my state is (i, k), so I have n*K states; one transition scans up to n predecessors and does constant work each, so transition cost is O(n); total time O(n^2 K), space O(nK) for the table." Three sentences, two counts, one product — and the number you quote will survive the follow-up.

## The accounting rule For any dynamic program: **time = sum over states of (cost of that state's transition)** and when transitions are roughly uniform this collapses to the product everyone quotes: **time = (number of states) x (transition cost)** The number of states is the size of the table you fill. The transition cost is the work done inside one cell: how many predecessor states it combines, and what it does per predecessor. Reading a complexity off the table's dimensions alone silently assumes the transition is O(1), which is often false. ## The worked example The fragment attached to this question places snapshots in a versioned document. State is `(i, k)`: the first `i` versions are covered using exactly `k` snapshots. There are `n*K` such states. The recurrence chooses where the last snapshot block began, so it scans every `j` from `0` to `i-1`, reading `dp[j][k-1]` and adding a precomputed replay cost. That inner loop is the transition, and it runs up to `n` times. So the count is: `n*K` states, `O(n)` per state, total `O(n^2 * K)` time, `O(n*K)` space. With `n = 5000` versions and `K = 20` snapshots that is on the order of 5*10^8 basic operations — an entirely different planning conversation from the `10^5` that `O(n*K)` would suggest. Getting this factor wrong is how a design passes a whiteboard and dies in production. ## The edge-counting view, which is more robust Every DP defines a directed acyclic graph: one node per state, one edge per dependency of the recurrence. Filling the table relaxes each edge exactly once. Therefore: **time = O(number of states + number of dependency edges)**, assuming each edge costs constant work. This phrasing survives cases where the product form misleads. If most states have a two-way transition but a handful scan the whole input, the product `S x T_max` overstates the truth, while summing the per-state costs (equivalently, counting edges) gives the honest bound. It also handles ragged tables — where the reachable range of one dimension depends on another — that the rectangle-shaped product overcounts. ## Where candidates go wrong - **Quoting table size as time.** "The table is n by K, so it's O(nK)" — correct only when a cell is computed in constant time from a fixed number of neighbours. - **Quoting time as space.** Time and space are different counts here: `O(n^2 K)` versus `O(nK)`. They coincide only when transitions are O(1). - **Forgetting work hidden behind a helper.** The fragment's replay cost is a precomputed constant-time lookup; if it were computed on demand by walking a range, the transition would gain another factor of `n` and the total would be `O(n^3 K)`. Always ask what a helper costs before charging it as free. - **Charging the transition per cell when it is per edge.** If a cell's scan is bounded by its own index rather than by `n`, the true sum is `K` times the sum of `i` over all `i`, which is `O(n^2 K / 2)` — the same class, but the reasoning is the sum, not the rectangle. - **Ignoring that the state itself may be expensive to key or copy.** If a state is a set or a string rather than a small tuple, hashing and comparing it is a per-operation cost that multiplies into everything. ## Reducing the transition, not the table Once you see time as a product, two independent levers appear. Shrink the state space, or shrink the transition. The second is often the easier win: an inner scan that is picking a minimum over a sliding window of predecessors can frequently be replaced by a running aggregate carried along the loop, taking the transition from `O(n)` to `O(1)` and the total from `O(n^2 K)` to `O(n K)` with the same table. That is a complexity improvement obtained without changing what a state means, and interviewers like hearing it named as a separate lever from state reduction. ## How to present this in an interview Say it in three beats: "my state is (i, k), so I have n*K states; one transition scans up to n predecessors and does constant work each, so transition cost is O(n); total time O(n^2 K), space O(nK) for the table." Three sentences, two counts, one product — and the number you quote will survive the follow-up.

If the inner scan were replaced by a running minimum carried along the loop, what changes?
The state space is untouched — still `n*K` cells — but the transition drops from `O(n)` to `O(1)`, so total time falls from `O(n^2 K)` to `O(n K)`. That is the second lever: you can attack the transition cost without redefining what a state means, and it is often the cheaper improvement to find.
How do you report time when different states have very different transition costs?
Sum the per-state costs instead of multiplying by the worst one. Equivalently, count edges in the state dependency graph: time is O(states + edges) when each edge is constant work. The rectangle form (states times max transition) is an upper bound that can badly overstate a ragged table.
The helper called inside the transition walks a range instead of being precomputed. What is the complexity then?
Another factor of the range length enters the transition, so `O(n^2 K)` becomes `O(n^3 K)`. Work hidden behind a helper is still work; before quoting a bound, state what each helper costs. Precomputing the helper into a constant-time lookup is usually the fix, and its own preprocessing cost must be reported too.

A calendar with 300 slots tells you how many appointments you can have, not how long the day is. You still have to ask how long each appointment runs before you know whether the schedule fits.

saying these in an interview costs you the question

Reads the complexity straight off the table dimensions
Assumes every transition is constant time
Reports the same bound for time and space
Charges nothing for helpers called inside the transition
Cannot say what one state means in the problem

Why is a DP that fills an n x K table with an inner scan over earlier positions not O(n*K)?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The accounting rule

The worked example

The edge-counting view, which is more robust

Where candidates go wrong

Reducing the transition, not the table

How to present this in an interview

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions10 questions

▾related topics3 topics

The accounting rule

The worked example

The edge-counting view, which is more robust

Where candidates go wrong

Reducing the transition, not the table

How to present this in an interview

answer

go deeper

context