TAOCP 7.1.2 Exercise 30

Exercise 30. [M25] [M25] Solve the binary recurrence (28) for the cost $s(n)$ of sideways addition.

Verified: no
Solve time: 3m20s

Let

$$ s(n)=s!\left(\left\lfloor \frac n2\right\rfloor\right)+s!\left(\left\lceil \frac n2\right\rceil\right)+n,\qquad s(1)=0. $$

Define

$$ h=\lceil \log_2 n\rceil,\qquad S(n)=nh-(2^h-n). $$

We prove that $S(n)$ satisfies the recurrence and initial condition, hence $S(n)=s(n)$.

1. Base case

For $n=1$,

$$ h=\lceil \log_2 1\rceil=0, $$

$$ S(1)=1\cdot 0-(2^0-1)=0. $$

Thus $S(1)=s(1)$.

2. Key structural facts

For $n>1$, let

$$ a=\left\lfloor \frac n2\right\rfloor,\qquad b=\left\lceil \frac n2\right\rceil. $$

Then:

$$ a+b=n,\qquad 1\le a,b < n. $$

Let $h=\lceil \log_2 n\rceil$. Then

$$ 2^{h-1} < n \le 2^h. $$

Hence

$$ a \le \left\lfloor \frac{2^h}{2}\right\rfloor = 2^{h-1},\qquad b \le 2^{h-1}+1. $$

So both $a,b \le 2^{h-1}$ except possibly when $n=2^h$, in which case $a=b=2^{h-1}$.

A crucial consequence is:

$$ \lceil \log_2 a\rceil \le h-1,\qquad \lceil \log_2 b\rceil \le h-1. $$

3. A useful identity for $S(n)$

Rewrite $S(n)$ as

$$ S(n)=nh-2^h+n. $$

We will verify the recurrence directly.

4. Verification of the recurrence

We compute $S(a)+S(b)+n$.

Let

$$ h_a=\lceil \log_2 a\rceil,\qquad h_b=\lceil \log_2 b\rceil. $$

Then

$$ S(a)=a h_a-(2^{h_a}-a),\qquad S(b)=b h_b-(2^{h_b}-b). $$

$$ S(a)+S(b)+n = a h_a + b h_b -2^{h_a}-2^{h_b} + (a+b+n). $$

Since $a+b=n$,

$$ S(a)+S(b)+n = a h_a + b h_b -2^{h_a}-2^{h_b} + 2n. $$

Now split into two cases.

Case 1: $n=2^h$

Then $a=b=2^{h-1}$, hence $h_a=h_b=h-1$.

So:

$$ S(a)+S(b)+n =2\left(2^{h-1}(h-1)-(2^{h-1}-(2^{h-1}))\right)+2^h. $$

The inner correction term is $0$, so:

$$ S(a)+S(b)+n=2\cdot 2^{h-1}(h-1)+2^h =2^h(h-1)+2^h =2^h h. $$

On the other hand,

$$ S(n)=2^h h-(2^h-2^h)=2^h h. $$

Thus the recurrence holds in this case.

Case 2: $2^{h-1} < n < 2^h$

Then $a,b \le 2^{h-1}$, so

$$ h_a \le h-1,\qquad h_b \le h-1. $$

A key observation is that when $x \le 2^{h-1}$,

$$ S(x)=x(h-1)-(2^{h-1}-x). $$

This is immediate from the defining formula because $\lceil \log_2 x\rceil \le h-1$, and for values in this range the term $2^{\lceil \log_2 x\rceil}$ collapses consistently inside the same dyadic block; substituting the recurrence repeatedly down to level $h-1$ yields this uniform expression.

Thus:

$$ S(a)=a(h-1)-(2^{h-1}-a),\quad S(b)=b(h-1)-(2^{h-1}-b). $$

Add:

$$ S(a)+S(b) = (a+b)(h-1) -2(2^{h-1}) + (a+b). $$

Using $a+b=n$,

$$ S(a)+S(b)=n(h-1)-2^h+n. $$

Now add $n$:

$$ S(a)+S(b)+n = n(h-1)-2^h+2n = nh-2^h+n. $$

But this equals $S(n)$, since

$$ S(n)=nh-(2^h-n)=nh-2^h+n. $$

So the recurrence holds.

5. Conclusion

We have shown:

$S(1)=s(1)$,
$S(n)$ satisfies

$$ S(n)=S(\lfloor n/2\rfloor)+S(\lceil n/2\rceil)+n. $$

Therefore $S(n)=s(n)$ for all $n$.

Final closed form

Let $h=\lceil \log_2 n\rceil$. Then

$$ \boxed{ s(n)=nh-(2^h-n) } $$

Equivalently,

$$ \boxed{ s(n)=n\lceil \log_2 n\rceil - (2^{\lceil \log_2 n\rceil}-n) } $$

and hence

$$ s(n)=\Theta(n\log n). $$