Why is interval DP O(n^3) when its dp table holds only O(n^2) entries?
answer
- Complexity is states times work per state
- How many distinct subranges exist?
- The transition itself contains a loop
- Count triples with the split strictly inside
- Divide the cube by six
basics
~20 sEach of the O(n^2) subranges is not filled in constant time: computing dp[i][j] scans every split point between i and j, which is up to O(n) work per entry. States times transitions-per-state gives O(n^2) * O(n) = O(n^3).
solid answer
~50 sComplexity in dynamic programming is **states multiplied by the work per state**, and interval DP is the standard case where people count only the states. There are about `n^2/2` subranges `[i, j]`, which is where the two visible nested loops come from. But filling one entry means minimising over every split point `k` strictly between `i` and `j` — a third loop of length up to `n`. So the total is O(n^3) time with O(n^2) space. Counted exactly, the triple loop visits every ordered triple `i < k < j`, which is `n(n-1)(n-2)/6`, roughly `n^3/6`. That constant matters in practice: at `n = 500` the naive cube is 1.25 * 10^8 but the real transition count is about 2 * 10^7, which is comfortable; at `n = 2000` it is about 1.3 * 10^9, which is not.
code
pseudocode · 12 linesfor i in 0..n-2
dp[i][i+1] = 0 // base: no split point fits inside
for span in 2..n-1 // shorter intervals first
for i in 0..n-1-span
j = i + span
best = INFINITY
for k in i+1..j-1 // the loop people forget to count
best = min(best, dp[i][k] + dp[k][j])
dp[i][j] = best + w(i, j)
// innermost line runs once per triple i < k < jgo deeper
Recall that a table of subranges has about n^2/2 entries and that filling one is not free here. Be able to say the cost is cubic in the sequence length and quadratic in memory.
Derive it out loud: count the states, then count the split points examined per state, then multiply. Expect to be pushed on why memoizing the same recurrence does not lower the bound.
Turn the bound into a feasibility call under a stated limit — a few hundred elements is fine, a few thousand is not — and name quadratic space, which cannot be rolled into a sliding window, as the constraint that usually binds first.
Own the decision of whether a cubic exact method belongs in a latency-sensitive path at all, and whether a cost function that admits a narrowed split search is worth the extra proof burden and maintenance cost for the team that inherits it.
## The formula people skip The running time of a dynamic program is **(number of distinct states) x (work to compute one state from already-solved states)** Both factors. The most common complexity error on this family is to read off the two nested loops that enumerate `i` and `j`, announce O(n^2), and stop. The transition itself contains a loop, and that loop is the whole point of interval DP. ## Counting the states A state is a contiguous subrange `[i, j]` with `i < j`. There are `n(n-1)/2` such pairs, so the state count is Theta(n^2). That is also the space bound if the table is materialised, and — as covered below — it is often the binding constraint before time is. ## Counting the transition The recurrence is ``` dp[i][j] = w(i, j) + min over i < k < j of ( dp[i][k] + dp[k][j] ) ``` Computing one entry evaluates the bracket once per candidate split point `k`. For a range of span `s = j - i` there are `s - 1` candidates, so the work per state grows with the state's own width, up to `n - 2` for the full range. Multiplying the Theta(n^2) states by the O(n) transition gives **O(n^3) time**. ## The exact count, and why the constant is worth knowing The triple loop visits exactly the ordered triples `i < k < j`, one per (state, split) pair. The number of such triples is `n(n-1)(n-2)/6`, about `n^3/6`. That factor of six is not a rounding detail when you are deciding feasibility on the spot: | chain length n | n^3 | actual transitions ~ n^3/6 | |---|---|---| | 100 | 10^6 | ~1.6 * 10^5 | | 500 | 1.25 * 10^8 | ~2.1 * 10^7 | | 1000 | 10^9 | ~1.7 * 10^8 | | 2000 | 8 * 10^9 | ~1.3 * 10^9 | The honest interview answer is O(n^3) *and* a feasibility read: a few hundred elements is routine, a thousand is a second or so of tight-loop work, several thousand needs a different plan. Quoting the raw cube without the divisor makes you reject inputs you could actually handle. ## What the profile is not **It is not O(n^2) because the table is two-dimensional.** Table dimensionality bounds space, not time. A two-dimensional table with a linear transition is cubic; a two-dimensional table with a constant transition is quadratic. You must inspect the recurrence to know which you have. **It is not improved by memoized recursion.** Writing the same recurrence top-down with memoization computes each state once and still loops over every split point inside, so it performs the same number of transitions. What changes is the constant factor (lookup overhead), the space profile (a recursion stack whose depth is part of the space cost), and the fact that unreachable states are skipped — which is a real win only when the reachable set is sparse, and for a dense interval table it is not. **It is not always O(n^3) for every problem of this shape.** For particular cost functions — those satisfying a quadrangle-inequality style condition, as the classic chain-combination and optimal-search-tree problems do — the search for the best split can be confined to a narrowing window bounded by the optimal splits of two neighbouring intervals. That is the Knuth-style optimisation, and it brings the total down to O(n^2). It is a differentiator, not a default: mention it as an available refinement, do not assume it applies to an arbitrary cost function, and never claim it without being able to say what condition the cost function has to satisfy. ## Space, which bites first O(n^2) space cannot be rolled down to O(n) the way a prefix DP often can. A prefix DP keeps a sliding window of one or two rows because state `i` reads only `i-1`. Here `dp[i][j]` reads `dp[i][k]` and `dp[k][j]` for arbitrary interior `k`, so entries from many different rows and columns stay live until the widest intervals are done. If you also want to *reconstruct* the optimal split structure rather than just its cost, you keep a second `n x n` table of the argmin split points. At `n = 3000` two such tables of eight-byte cells run to roughly 140 MB, which is a memory ceiling long before the time bound becomes interesting. ## How to say it in an interview "Theta(n^2) states, one per subrange; O(n) work per state to scan the split point; so O(n^3) time and O(n^2) space, with the transition count about `n^3/6` since only triples with the split strictly inside count. Space is usually what limits me first, because the table does not compress to a rolling window." That answer shows the formula, the constant, and the real constraint.
- Does solving it top-down with memoization change the complexity?No. Memoized recursion computes each subrange once and still scans every split point inside it, so the transition count is identical and the time stays O(n^3). What changes is the constant factor from lookup overhead, and the space profile: the recursion stack counts toward space complexity. Top-down only wins when many states are unreachable, and for a dense interval table almost all of them are reachable.
- Can an interval DP ever beat O(n^3)?For some cost functions, yes. When the cost satisfies a quadrangle-inequality style condition — which the classic chain-combination and optimal-search-tree formulations do — the optimal split point is monotone, so the search for it can be restricted to the window between the optimal splits of two neighbouring intervals. Summed over the table that telescopes to O(n^2). Treat it as a refinement you name when the cost function qualifies, never as a general property of interval DP.
- Can the O(n^2) table be compressed to linear space?Generally no. A prefix DP compresses because row `i` reads only row `i-1`; here an entry reads entries at arbitrary interior split points, so cells from many rows and columns stay live until the widest intervals are computed. If you also need to reconstruct the optimal split structure you keep a second table of argmin splits, doubling it. In practice the quadratic space ceiling is hit before the cubic time ceiling.
saying these in an interview costs you the question
- Says O(n^2) after counting only the i and j loops
- Assumes a two-dimensional table implies quadratic time
- Claims memoization makes it quadratic
- Quotes n^3 as the transition count, ignoring the divisor
- Assumes the split-point search can always be narrowed
- Thinks the table rolls down to two rows like a prefix DP