The optimal binary search tree dynamic program is naively O(n^3). State the monotonicity condition that reduces it to O(n^2) and explain how the reduced recurrence uses it.

The optimal binary search tree dynamic program is naively O(n^3). State the monotonicity condition that reduces it to O(n^2) and explain how the reduced recurrence uses it.

Approach: The inner loop searches for the best root over an interval. Bound the search range using the optimal roots of the two intervals one shorter.

O(n^2), by Knuth optimisation using the monotonicity opt[i][j-1] <= opt[i][j] <= opt[i+1][j] on the optimal root. The base recurrence is cost[i][j] = W(i,j) + min over r in [i,j] of cost[i][r-1] + cost[r+1][j], where W is the total probability weight of the interval, and the naive inner scan over r makes it cubic. When the weight function satisfies the quadrangle inequality W(i,j) + W(i',j') <= W(i',j) + W(i,j'), which sums of non-negative probabilities do, the optimal root is monotone in both endpoints, so the scan for opt[i][j] can be restricted to the range between opt[i][j-1] and opt[i+1][j]. Summing those range lengths along one diagonal telescopes to O(n), because consecutive ranges share endpoints, so each of the n diagonals costs O(n) and the total is O(n^2). The same argument gives O(n^2) for matrix chain style problems whose cost obeys the quadrangle inequality, and it fails as soon as the inequality does, in which case the inner loop is genuinely linear.

Follow-up: What does the Hu-Tucker algorithm achieve for the same problem and at what cost?

Key concepts: knuth optimisation, monotone root, quadrangle inequality, amortised inner loop.