TAOCP 5.3.2 Exercise 21

Let $M(m,n)$ be Knuth’s function from Section 5.

taocpmathematicsalgorithmsvolume-3math-research

Section 5.3.2: Minimum-Comparison Merging

Exercise 21. [M47] [M47] Prove or disprove (23) and (24).

Verified: no
Solve time: 1m39s

Let $M(m,n)$ be Knuth’s function from Section 5.3.2: the maximum cost (in pointer traversals, or equivalent unit-cost steps as defined in the section) of performing any sequence of $m$ FIND operations and $n$ UNION operations on a disjoint-set data structure, under the specified heuristics.

The statements

Equations (23) and (24) assert the monotonicity of $M(m,n)$ in each argument:

$$ (23)\quad M(m,n) \le M(m,n+1), $$

$$ (24)\quad M(m,n) \le M(m+1,n). $$

Proof of (23)

Fix $m,n \ge 0$. Consider any sequence $S$ of $m$ FIND operations and $n$ UNION operations. By definition, the cost of $S$ is at most $M(m,n)$.

From such a sequence $S$, construct a new sequence $S'$ consisting of the same $m$ FIND operations and $n+1$ UNION operations, where the additional UNION is performed on two elements already in the same set. This extra UNION does not change the structure in any way that increases efficiency beyond the original sequence, and it does not reduce the cost of any FIND operations already present.

Thus every sequence counted in $M(m,n)$ corresponds to a sequence counted among those considered in $M(m,n+1)$, and the maximum over a larger class of sequences cannot be smaller. Hence,

$$ M(m,n) \le M(m,n+1). $$

Proof of (24)

Fix $m,n \ge 0$. Let $S$ be any sequence of $m$ FIND operations and $n$ UNION operations.

Construct a new sequence $S''$ consisting of $m+1$ FIND operations and $n$ UNION operations by appending an additional FIND operation on any element already present.

This extra FIND cannot reduce the cost of any prior operations, and it adds nonnegative cost itself. Therefore the class of sequences considered in $M(m+1,n)$ strictly contains (in the sense of restriction by deleting the last FIND) all sequences considered in $M(m,n)$, up to ignoring the final operation.

Taking maxima, enlarging the allowed number of FIND operations cannot decrease the worst-case cost, so

$$ M(m,n) \le M(m+1,n). $$

Conclusion

Both inequalities are valid monotonicity properties of the worst-case disjoint-set operation cost function:

$$ M(m,n) \le M(m,n+1), \qquad M(m,n) \le M(m+1,n). $$

Thus, both (23) and (24) are true.