TAOCP 5.3.2 Exercise 4

Let $\underline{M}(m,n)$ denote the lower-bound function for merging described in Section 5.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.3.2: Minimum-Comparison Merging

Exercise 4. [M42] [M42] Is $\underline{M}(m,n) > [\lg \binom{m+n}{m}]$ for all $m$ and $n$?

Verified: yes
Solve time: 1m14s

Setup

Let $\underline{M}(m,n)$ denote the lower-bound function for merging described in Section 5.3.2, and let $\left[\lg x\right]$ denote the greatest integer not exceeding $\lg x$. The question asks whether

$\underline{M}(m,n) > \left[\lg \binom{m+n}{m}\right]$

holds for all integers $m,n \ge 1$.

To disprove the statement, it suffices to exhibit a single pair $(m,n)$ for which

$\underline{M}(m,n) \le \left[\lg \binom{m+n}{m}\right].$

Solution

Take $m=1$ and $n=1$. From Table 1 in Section 5.3.2, the adversary lower bound gives

$\underline{M}(1,1)=1.$

Next compute the information-theoretic term. Since

$\binom{m+n}{m}=\binom{2}{1}=2,$

we have

$\lg \binom{2}{1}=\lg 2=1,$

hence

$\left[\lg \binom{2}{1}\right]=1.$

Thus,

$\underline{M}(1,1)=\left[\lg \binom{2}{1}\right].$

This contradicts the strict inequality requirement $\underline{M}(m,n) > \left[\lg \binom{m+n}{m}\right]$ for all $m,n$.

Verification

The value $\underline{M}(1,1)=1$ agrees with the base case structure of the adversary construction, since a single comparison is necessary to merge two single-element lists.

The combinatorial bound satisfies

$\binom{2}{1}=2,$

and therefore its binary logarithm is exactly $1$, so the integer part is also $1$.

All quantities are consistent under the definitions used in Section 5.3.2.

Conclusion

The inequality fails at $(m,n)=(1,1)$, since both sides equal $1$. Therefore the statement is false.

$\boxed{\text{No}}$