TAOCP 7.1.4 Exercise 70

Exercise 70. [21] [21] Discuss setting b to ⌊lg LCOUNT[l]⌋instead of ⌈lg LCOUNT[l]⌉in step S4.

Verified: yes
Solve time: 1m33s

Solution

Let $LCOUNT[l]$ denote the number of nodes (or items) that must be accommodated at level $l$ in step S4 of Algorithm S, and let $b$ determine a table size $2^b$ used for storage at that level.

The original choice $b = \lceil \lg LCOUNT[l] \rceil$ ensures the fundamental inequality

$2^b \ge LCOUNT[l] > 2^{b-1}.$

This follows directly from the definition of the ceiling function applied to $\lg LCOUNT[l]$. Consequently, the allocated structure always has capacity at least equal to the number of items that must be inserted at level $l$.

Now replace the assignment by $b = \lfloor \lg LCOUNT[l] \rfloor$. Then

$2^b \le LCOUNT[l] < 2^{b+1}.$

More precisely, whenever $LCOUNT[l]$ is not an exact power of two, one has

$2^b \le LCOUNT[l] - 1,$

since $b < \lg LCOUNT[l] < b+1$ implies $2^b < LCOUNT[l]$ and both sides are integers.

The consequence is that the allocated capacity $2^b$ fails to dominate the required occupancy $LCOUNT[l]$ in all cases where $LCOUNT[l]$ is not a power of two. In such cases, at least one insertion into the level-$l$ structure cannot be accommodated without overflow or collision-resolution beyond the intended design of Algorithm S. The algorithmic invariant that every node at level $l$ has a distinct place in a table of size $2^b$ is therefore violated.

The only case where correctness is preserved under the modification is when $LCOUNT[l] = 2^k$ for some integer $k$. Then $\lfloor \lg LCOUNT[l] \rfloor = \lceil \lg LCOUNT[l] \rceil = k$, and both choices coincide, yielding exact fit.

The structural effect of using the floor function is thus a systematic reduction of table size from the least power of two that is sufficient to the greatest power of two that is insufficient except at exact powers of two. This changes the guarantee

$2^b \ge LCOUNT[l]$

into

$2^b \le LCOUNT[l],$

which reverses the safety condition required by the allocation strategy.

From the perspective of Algorithm S, this modification trades space for correctness: memory usage decreases by up to a factor approaching $2$ when $LCOUNT[l]$ lies just above a power of two, but the algorithm loses its guarantee of successful completion without overflow handling or reallocation logic.

This completes the analysis. ∎