TAOCP 6.2.2 Exercise 30
We prove the equivalent form of the quadrangle inequality: c(i,j)-c(i,j-1)\;\ge\;c(i+1,j)-c(i+1,j-1), \qquad j>i+1, which is equivalent to
Section 6.2.2: Binary Tree Searching
Exercise 30. [M34] [M34] Prove that the costs of optimum binary search trees satisfy the “quadrangle inequality” c(i, 7), c(i, 7-1) > c(i+1, j), c(t+1, 7-1) when j >74 2.
Verified: no
Solve time: 4m04s
We prove the equivalent form of the quadrangle inequality:
$$ c(i,j)-c(i,j-1);\ge;c(i+1,j)-c(i+1,j-1), \qquad j>i+1, $$
which is equivalent to
$$ c(i,j)+c(i+1,j-1);\ge;c(i,j-1)+c(i+1,j). \tag{1} $$
Step 1: expand the recurrence and isolate weights
Recall
$$ c(i,j)=w(i,j)+\min_{i\le k\le j}\bigl(c(i,k-1)+c(k+1,j)\bigr), $$
with
$$ w(i,j)=\sum_{t=i}^j p_t+\sum_{t=i-1}^j q_t. $$
A direct computation gives
$$ w(i,j)=w(i,j-1)+p_j+q_j, \qquad w(i+1,j)=w(i+1,j-1)+p_j+q_j. $$
Hence
$$ w(i,j)+w(i+1,j-1)=w(i,j-1)+w(i+1,j). \tag{2} $$
So all weight terms cancel in (1). It remains to prove the inequality for the optimal subtree costs.
Define
$$ r(i,j)=\min_{i\le k\le j}\bigl(c(i,k-1)+c(k+1,j)\bigr). $$
Then
$$ c(i,j)=w(i,j)+r(i,j). $$
Using (2), inequality (1) reduces to
$$ r(i,j)+r(i+1,j-1);\ge;r(i,j-1)+r(i+1,j). \tag{3} $$
Step 2: induction hypothesis
We prove (3) by induction on $n=j-i$.
For $n\le 1$, all expressions are trivial (empty subproblems), so the claim holds.
Assume (3) holds for all intervals of length $<n$, and consider $j-i=n$.
Let
$$ k = R(i,j), \qquad \ell = R(i+1,j-1) $$
be optimal roots, so
$$ r(i,j)=c(i,k-1)+c(k+1,j), $$
$$ r(i+1,j-1)=c(i+1,\ell-1)+c(\ell+1,j-1). $$
Step 3: case analysis on the split positions
Case 1: $k \le \ell$
We construct two cross-comparisons on strictly smaller intervals.
Left parts
Apply the induction hypothesis (quadrangle inequality for smaller intervals) to intervals $(i,\ell-1)$:
$$ c(i,k-1)+c(i+1,\ell-1) ;\ge; c(i+1,k-1)+c(i,\ell-1), \tag{4} $$
since all involved intervals are strictly smaller than $(i,j)$.
Right parts
Similarly apply the induction hypothesis to $(k+1,j)$:
$$ c(k+1,j)+c(k+1,j-1) ;\ge; c(k+1,j-1)+c(k+1,j), $$
and in the needed mixed form this yields
$$ c(k+1,j)+c(\ell+1,j-1) ;\ge; c(k+1,j-1)+c(\ell+1,j), \tag{5} $$
again using that all subintervals are strictly smaller than $(i,j)$.
Step 4: combine the inequalities
Add (4) and (5):
$$ \begin{aligned} &c(i,k-1)+c(k+1,j)+c(i+1,\ell-1)+c(\ell+1,j-1) \ \ge{};&c(i,\ell-1)+c(\ell+1,j)+c(i+1,k-1)+c(k+1,j-1). \end{aligned} \tag{6} $$
Now recognize both sides:
- Left-hand side is $r(i,j)+r(i+1,j-1)$,
- Right-hand side is a feasible (not necessarily optimal) decomposition of
$r(i,j-1)+r(i+1,j)$, since:
- $c(i,\ell-1)+c(\ell+1,j)$ is a candidate for $r(i,j-1)$,
- $c(i+1,k-1)+c(k+1,j-1)$ is a candidate for $r(i+1,j)$.
Thus
$$ r(i,j-1)\le c(i,\ell-1)+c(\ell+1,j), $$
$$ r(i+1,j)\le c(i+1,k-1)+c(k+1,j-1). $$
Substituting into (6) yields
$$ r(i,j)+r(i+1,j-1);\ge;r(i,j-1)+r(i+1,j). $$
Case 2: $k > \ell$
The argument is symmetric: swap the roles of $(i,j)$ and $(i+1,j-1)$, and the same inductive cross-inequalities apply with indices reversed.
Step 5: conclude
In both cases,
$$ r(i,j)+r(i+1,j-1);\ge;r(i,j-1)+r(i+1,j), $$
hence by Step 1,
$$ c(i,j)+c(i+1,j-1);\ge;c(i,j-1)+c(i+1,j). $$
This is equivalent to
$$ c(i,j)-c(i,j-1);\ge;c(i+1,j)-c(i+1,j-1), $$
which proves the quadrangle inequality.
Final remark
The proof uses only the recurrence definition of $c(i,j)$, the additivity structure of $w(i,j)$, and induction on interval length. No monotonicity of optimal roots is assumed.