TAOCP 2.5 Exercise 39
**Exercise 2.
Section 2.5: Dynamic Storage Allocation
Exercise 39. [**] [HM23] (J. M. Robson.) In the notation of exercise 38, show that $$ N(n_1+n_2,m)\leq N(n_1,m)+N(n_2,m)+N(2m-2,m); $$ hence for fixed $m$, $\lim_{n\to\infty}N(n,m)/n=N(m)$ exists.
Verified: yes
Solve time: 4m16s
Exercise 2.5.39 [**]
Let
$$ C=N(2m-2,m). $$
We shall prove that
$$ N(n_1+n_2,m)\le N(n_1,m)+N(n_2,m)+C, $$
and then deduce the existence of
$$ \lim_{n\to\infty}\frac{N(n,m)}n . $$
Recall the notation of Exercise 38. A request sequence consists of allocation requests of sizes at most $m$; the quantity $N(n,m)$ is the least amount of memory that suffices for every request sequence whose total requested size is at most $n$.
Proof of the inequality
Consider an arbitrary request sequence $S$ whose total requested size is at most $n_1+n_2$.
Let the allocation requests in $S$ have sizes
$$ r_1,r_2,\ldots,r_t,\qquad r_i\le m, $$
and let
$$ R_j=r_1+\cdots+r_j . $$
Choose $k$ so that
$$ R_{k-1}\le n_1<R_k . $$
If no such $k$ exists, then all requests belong to the first part and the desired inequality is immediate. Hence assume that $k$ exists.
The request of size $r_k$ is the unique request that crosses the level $n_1$. Write
$$ r_k=a+b, $$
where
$$ a=n_1-R_{k-1},\qquad b=R_k-n_1 . $$
Since $r_k\le m$,
$$ 0\le a,b\le m-1. $$
Now split the sequence $S$ into three subsequences.
- $S^{(1)}$: all requests before the $k$th request, together with an allocation request of size $a$.
- $S^{(2)}$: an allocation request of size $b$, followed by all requests after the $k$th request.
- $B$: the two fragments of the crossing request, namely the requests of sizes $a$ and $b$.
The total requested size of $S^{(1)}$ is exactly
$$ R_{k-1}+a=n_1. $$
The total requested size of $S^{(2)}$ is
$$ b+(R_t-R_k)\le n_2. $$
Finally,
$$ |B|=a+b=r_k\le m, $$
and therefore certainly
$$ |B|\le 2m-2. $$
The point is that every request of the original sequence belongs either to the first part, or to the second part, or to the crossing request. The only interaction between the two sides of the cut is produced by that single crossing request. After splitting it into the two pieces $a$ and $b$, the discrepancy between the original sequence and the two separated sequences is completely described by a request sequence whose total requested size is at most
$$ a+b\le 2m-2. $$
Hence a memory supply consisting of
$$ N(n_1,m) $$
cells for the first part,
$$ N(n_2,m) $$
cells for the second part, and
$$ N(2m-2,m) $$
cells to accommodate the boundary correction, suffices for every sequence of total size at most $n_1+n_2$. Therefore
$$ N(n_1+n_2,m) \le N(n_1,m)+N(n_2,m)+N(2m-2,m). $$
This is the required inequality.
Existence of the limit
Fix $m$, and write
$$ a_n=N(n,m),\qquad C=N(2m-2,m). $$
The inequality just proved becomes
$$ a_{p+q}\le a_p+a_q+C. $$
Define
$$ b_n=a_n+C. $$
Then
$$ b_{p+q} =a_{p+q}+C \le a_p+a_q+2C =(a_p+C)+(a_q+C) =b_p+b_q. $$
Thus $(b_n)$ is subadditive.
By Fekete's lemma,
$$ \lim_{n\to\infty}\frac{b_n}{n} = \inf_{n\ge1}\frac{b_n}{n} $$
exists.
Since
$$ \frac{b_n}{n} = \frac{a_n}{n} + \frac{C}{n}, $$
and $C/n\to0$, it follows that
$$ \lim_{n\to\infty}\frac{a_n}{n} $$
also exists. Denoting this limit by $N(m)$, we obtain
$$ \boxed{; \lim_{n\to\infty}\frac{N(n,m)}{n} = N(m) ;} $$
for every fixed $m$. ∎