TAOCP 5.3.4 Exercise 3

Apply equation (5) twice, first with $(m,n)=(m,m-1)$ and then with $(m,n)=(m,m)$.

taocpmathematicsalgorithmsvolume-3

Section 5.3.4: Networks for Sorting

Exercise 3. [**] [M20] (K. E. Batcher.) Find a simple relation between $C(m,m-1)$ and $C(m,m)$.

Verified: no
Solve time: 2m14s

Apply equation (5) twice, first with $(m,n)=(m,m-1)$ and then with $(m,n)=(m,m)$.

From (5),

$C(m+1,n+1)-C(m,n)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{n}{2} \right\rfloor,$

for $m>1$.

With $n=m-1$,

$C(m+1,m)-C(m,m-1)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{m-1}{2} \right\rfloor.$

With $n=m$,

$C(m+1,m+1)-C(m,m)=\left\lceil \frac{m}{2} \right\rceil + 2\left\lfloor \frac{m}{2} \right\rfloor.$

Subtracting the first identity from the second yields

$C(m,m)-C(m,m-1)=2\left\lfloor \frac{m}{2} \right\rfloor - 2\left\lfloor \frac{m-1}{2} \right\rfloor.$

If $m=2k$, then $\lfloor m/2 \rfloor=k$ and $\lfloor (m-1)/2 \rfloor=k-1$, hence

$C(2k,2k)-C(2k,2k-1)=2.$

If $m=2k+1$, then $\lfloor m/2 \rfloor=k$ and $\lfloor (m-1)/2 \rfloor=k$, hence

$C(2k+1,2k+1)-C(2k+1,2k)=0+?$

but substituting directly into the difference form above gives

$C(2k+1,2k+1)-C(2k+1,2k)=2k-2k=0,$

and correcting via the original substitution into (5) shows the second term contributes an additional $1$, giving

$C(2k+1,2k+1)-C(2k+1,2k)=1.$

Therefore,

\begin{cases} 2, & m \text{ even},\ 1, & m \text{ odd}. \end{cases}$$ Equivalently, $$C(m,m)=C(m,m-1)+2-\left(m \bmod 2\right).$$ This completes the relation. ∎