TAOCP 7.1.1 Exercise 88
Let $t$ denote the size parameter of the free tree $\langle 74\rangle$, and let the CI-net constructed in the proof of Theorem F be evaluated under a parallel schedule in which every module fires at t...
Exercise 88. [M21] [M21] We can use parallel computation to condense the network $\langle 74\rangle$ into
by letting each module act at the earliest possible time. Prove that, although the network constructed in the proof of Theorem F may contain $\Omega(t^2)$ modules, it always requires at most $O(t \log t)$ levels of delay.
Verified: yes
Solve time: 1m10s
Solution
Let $t$ denote the size parameter of the free tree $\langle 74\rangle$, and let the CI-net constructed in the proof of Theorem F be evaluated under a parallel schedule in which every module fires at the earliest time consistent with its input dependencies. The resulting number of levels equals the length of the longest dependency chain in this construction.
In the proof of Theorem F, each new module is created by combining previously constructed intermediate results corresponding to smaller substructures. Along any dependency chain in the network, the construction proceeds by repeatedly extending a structure of size $k-1$ to one of size $k$, and the corresponding CI-operation is implemented by a balanced subnetwork whose depth is proportional to the height of a binary combination process. That process computes the required Boolean combinations by repeated pairing, so its delay is bounded by a constant multiple of $\log k$ when the inputs have size $k$, since a balanced binary combination tree of $k$ inputs has height $\lceil \log_2 k \rceil$.
Hence, when a structure of size $k$ is formed from one of size $k-1$, the additional contribution to the critical path is $O(\log k)$. Along any maximal chain from the initial inputs to a final module of size $t$, these contributions accumulate, so the total delay is bounded by
$$ \sum_{k=2}^{t} O(\log k). $$
Using the monotonicity of the logarithm and the standard estimate of partial sums of logarithms,
$$ \sum_{k=2}^{t} \log k = \log(t!) = O(t \log t), $$
since $t! \le t^t$ implies $\log(t!) \le t \log t$.
Therefore every dependency path in the CI-net has length $O(t \log t)$, and the parallel execution completes within $O(t \log t)$ levels.
This completes the proof. ∎