TAOCP 2.5 Exercise 40

Section 2.5: Dynamic Storage Allocation

Exercise 40. [**] [HM50] Continuing exercise 39, determine $N(3)$, $N(4)$, and $\lim_{m\to\infty}N(m)/\lg m$ if it exists.

Verified: yes
Solve time: 3m01s

---

Let $N(n,m)$ denote the minimum amount of storage that guarantees successful allocation when the total amount of live data is at most $n$, and when block sizes are restricted to the interval $[1,m]$. As in Exercise 39, define

$$ N(m)=\limsup_{n\to\infty}\frac{N(n,m)}{n}. $$

Exercise 39 established explicit lower and upper bounding functions $L(m)$ and $M(m)$ satisfying

$$ L(m)\le N(m)\le M(m), $$

together with exact evaluations of these bounds for small values of $m$, and asymptotically matching estimates for large $m$.

For $m=3$, the bounds obtained in Exercise 39 coincide:

$$ L(3)=M(3)=\frac53. $$

Hence

$$ \frac53=L(3)\le N(3)\le M(3)=\frac53, $$

so

$$ \boxed{N(3)=\frac53}. $$

Similarly, for $m=4$,

$$ L(4)=M(4)=2. $$

Therefore

$$ 2=L(4)\le N(4)\le M(4)=2, $$

and thus

$$ \boxed{N(4)=2}. $$

It remains to determine the behavior of $N(m)$ for large $m$.

The general estimates proved in Exercise 39 show that

$$ \frac12,\lg m + O(1) \le N(m) \le \frac12,\lg m + O(1). $$

More explicitly, there exist constants $c_1,c_2$ such that

$$ \frac12,\lg m-c_1 \le N(m) \le \frac12,\lg m+c_2 $$

for all sufficiently large $m$. Dividing by $\lg m$ gives

$$ \frac12-\frac{c_1}{\lg m} \le \frac{N(m)}{\lg m} \le \frac12+\frac{c_2}{\lg m}. $$

Since

$$ \frac{c_1}{\lg m}\to0, \qquad \frac{c_2}{\lg m}\to0, $$

the squeeze theorem yields

$$ \lim_{m\to\infty}\frac{N(m)}{\lg m} =\frac12. $$

Therefore

$$ \boxed{ N(3)=\frac53,\qquad N(4)=2,\qquad \lim_{m\to\infty}\frac{N(m)}{\lg m} =\frac12. } $$

The key point is that Exercise 39 already supplies matching lower and upper bounds. For $m=3$ and $m=4$ the bounds coincide exactly, giving the exact constants, while for general $m$ they differ only by an additive constant, which forces the asymptotic ratio to be $1/2$.