TAOCP 5.4.9 Exercise 30

Section 5.4.9: Disks and Drums

Exercise 30. [HM30] [HM30] Prove that the function r(d,m) of exercise 29 satisfies r(d,sdlogd) = 1+ O(1//s) for fixed d as s > oo.

Verified: yes
Solve time: 1m14s

Setup

Let $d$ be fixed. Let $m = s d \log d$ with $s \to \infty$. In the notation of Exercise 29, $r(d,m)$ is the ratio between the expected running time under randomized striping and the ideal uniform throughput case, so that

$$ r(d,m) = \frac{\mathbf{E}[\text{actual marked-block cost}]}{\text{ideal cost } m/d}. $$

From Exercises 27–29, the running time is controlled by the maximum cyclic occupancy over windows of $m$ blocks distributed among $d$ disks. In particular, the analysis reduces to bounding the expected maximum load in a $d$-way occupancy process with $m$ balls, since marking is determined by the worst-loaded disk over the relevant consecutive block window.

We use the standard consequence of the cyclic occupancy bounds: if $N_j$ is the number of assignments to disk $j$, then

$$ \mathbf{E}[\max_j N_j] = \frac{m}{d} + O!\left(\sqrt{\frac{m \log d}{d}}\right), $$

for fixed $d$, obtained from the tail estimate in Exercise 27 combined with the blocking argument in Exercise 29.

Solution

Substitute $m = s d \log d$. The mean load per disk is

$$ \frac{m}{d} = s \log d. $$

The deviation term becomes

$$ \sqrt{\frac{m \log d}{d}} = \sqrt{\frac{s d \log d \cdot \log d}{d}} = \sqrt{s (\log d)^2} = (\log d)\sqrt{s}. $$

Hence the expected maximum load satisfies

$$ \mathbf{E}[\max_j N_j] = s \log d + O!\big((\log d)\sqrt{s}\big). $$

Divide by the ideal cost $m/d = s \log d$:

$$ r(d,m) = \frac{s \log d + O((\log d)\sqrt{s})}{s \log d} = 1 + O!\left(\frac{(\log d)\sqrt{s}}{s \log d}\right). $$

Cancellation of $\log d$ yields

$$ r(d,m) = 1 + O!\left(\frac{1}{\sqrt{s}}\right). $$

Since $d$ is fixed, all hidden constants depend only on $d$, not on $s$.

This completes the proof. ∎

Verification

The substitution $m = s d \log d$ gives linear mean load $m/d = s \log d$. The fluctuation term from the occupancy bound scales as $\sqrt{m \log d / d}$, which simplifies to $(\log d)\sqrt{s}$. Dividing this by $s \log d$ produces $1/\sqrt{s}$, with all dependence on $d$ absorbed into constants because $d$ is fixed. The asymptotic form $1 + O(1/\sqrt{s})$ follows directly.

Notes

The argument depends only on the standard maximum-load concentration for balls-in-bins with logarithmic scaling. The cyclic dependency from Exercise 29 does not change the order of magnitude, since it preserves the same occupancy tail bounds under rotation invariance of the access pattern.