TAOCP 2.2.2 Exercise 17

Let C=L_\infty-L_0 be the total amount of available memory.

taocpmathematicsalgorithmsvolume-1hard

Section 2.2.2: Sequential Allocation

Exercise 17. [30] If $\sigma$ is any sequence of insertions and deletions such as (12), let $s_0(\sigma)$ be the number of stack overflows that occur when the simple method of Fig. 4 is applied to $\sigma$ with initial conditions (11), and let $s_1(\sigma)$ be the corresponding number of overflows with respect to other initial conditions such as (13). Prove that $s_0(\sigma) \le s_1(\sigma) + L_\infty - L_0$.

Verified: no
Solve time: 44s

Setup

Let

$$ C=L_\infty-L_0 $$

be the total amount of available memory.

For a sequence $\sigma$ of insertions and deletions, let $s_0(\sigma)$ denote the number of overflows produced by the simple method of Fig. 4 when the initial conditions are those of (11):

$$ \text{BASE}[j]=\text{TOP}[j]=L_0 \qquad (1\le j\le n). $$

Let $s_1(\sigma)$ denote the number of overflows produced when an arbitrary alternative set of initial conditions is used, for example (13).

The problem is to prove

$$ s_0(\sigma)\le s_1(\sigma)+C. $$

For each stack $j$, write

$$ a_j=\text{BASE}[j]-L_0 $$

for its initial allocation under the alternative initial conditions. Since all stacks lie in the common memory area,

$$ 0=a_1\le a_2\le\cdots\le a_n\le C, $$

and therefore

$$ \sum_{j=1}^{n-1}(a_{j+1}-a_j)=a_n\le C. \tag{1} $$

The quantity

$$ g_j=a_{j+1}-a_j \qquad (1\le j<n) $$

is the number of memory locations initially reserved between stacks $j$ and $j+1$.

Solution

Fix the sequence $\sigma$.

Consider a particular overflow that occurs under the alternative initial conditions. Such an overflow is caused by some stack $i$. Immediately before the overflow, stack $i$ has expanded far enough to reach its current boundary. Relative to the initial configuration, at least one unit of the initial gap adjacent to stack $i$ has been consumed.

Associate this overflow with one such consumed unit of initial gap. Since one unit of gap disappears when it is first crossed, no unit of initial gap can be associated with more than one overflow.

The total number of units of initial gap is

$$ \sum_{j=1}^{n-1} g_j = \sum_{j=1}^{n-1}(a_{j+1}-a_j) \le C $$

by (1). Hence at most $C$ overflows under the alternative initial conditions can be charged to distinct units of initial gap.

After all initial gaps have been exhausted, the memory configuration obtained from the alternative initial conditions differs from the configuration obtained from (11) only by a translation of blocks of occupied cells. No unused memory remains that was present solely because of the initial allocation. Therefore every subsequent overflow under the alternative initial conditions must also occur under the initial conditions (11). In other words, once the advantage supplied by the initial gaps has been used up, the two methods have exactly the same possibilities for further growth.

Consequently the only overflows that can occur under (11) but not under the alternative initial conditions are those prevented by the initial reserve space represented by the gaps $g_j$. There are at most

$$ \sum_{j=1}^{n-1} g_j\le C $$

such overflows.

Thus

$$ s_0(\sigma)-s_1(\sigma)\le C, $$

which is equivalent to

$$ s_0(\sigma)\le s_1(\sigma)+L_\infty-L_0. $$

This completes the proof.

∎

Verification

The proof depends on two facts.

First, the total extra advantage supplied by arbitrary initial allocations is exactly the total number of initially unused locations separating neighboring stacks. Formula (1) shows that this quantity is at most $L_\infty-L_0$.

Second, each overflow avoided by the alternative initial allocation must consume at least one previously unused unit of that initial reserve. A reserve unit can be consumed only once. Therefore no more than $L_\infty-L_0$ overflows can be avoided.

Hence the excess of $s_1(\sigma)$ over $s_0(\sigma)$ can never exceed $L_\infty-L_0$, giving the stated inequality.

Notes

The argument shows a stronger statement. If

$$ R=\sum_{j=1}^{n-1}(\text{BASE}[j+1]-\text{BASE}[j]) $$

is the total reserve space present initially, then

$$ s_0(\sigma)\le s_1(\sigma)+R. $$

Since $R\le L_\infty-L_0$, the required bound follows immediately.