TAOCP 2.2.2 Exercise 18

Section 2.2.2: Sequential Allocation

Exercise 18. [M30] Show that the total running time for any sequence of $m$ insertions and/or deletions by Algorithms G and R is

$$ O\left(m + n\sum_{k=1}^{m}\frac{\alpha_k}{1-\alpha_k}\right), $$

where $\alpha_k$ is the fraction of memory occupied on the most recent repacking previous to the $k$th operation; $\alpha_k = 0$ before the first repacking. (Therefore if the memory never gets more than, say, 90% full, each operation takes at most $O(n)$ units of time in an amortized sense, regardless of the total memory size.) Assume that $L_\infty - L_0 \ge n^2$.

Verified: no
Solve time: 46s

---

Setup

Let $N=L_\infty-L_0$ be the total memory size. By hypothesis, $N\ge n^2$.

Consider an arbitrary sequence of $m$ stack operations, insertions and deletions, executed using Algorithms $G$ and $R$. Let $T(m)$ denote the total running time. We must prove

$$ T(m) = O\left( m+n\sum_{k=1}^{m}\frac{\alpha_k}{1-\alpha_k} \right), $$

where $\alpha_k$ is the fraction of memory occupied immediately after the most recent repacking preceding the $k$th operation, and $\alpha_k=0$ before the first repacking.

Let the successive repackings occur at times

$$ 1\le r_1<r_2<\cdots<r_t\le m. $$

For the interval beginning immediately after repacking $r_j$ and ending just before repacking $r_{j+1}$, let

$$ \alpha^{(j)} $$

be the occupied-memory fraction after repacking $r_j$. Thus for every operation $k$ in this interval,

$$ \alpha_k=\alpha^{(j)}. $$

Algorithm $R$ performs the actual relocation of stack contents prescribed by Algorithm $G$. Its cost is proportional to the number of stacks plus the amount of occupied memory moved. Since all occupied locations are scanned during a repacking, the running time of one repacking is

$$ O(n+\alpha N), $$

where $\alpha$ is the occupancy fraction immediately after the preceding repacking.

The ordinary insertion or deletion work between repackings costs $O(1)$ per operation, contributing $O(m)$ altogether. It therefore suffices to bound the total cost of all repackings.

Solution

Fix one repacking interval, beginning immediately after some repacking with occupancy fraction $\alpha$, and ending when the next overflow occurs.

Immediately after the repacking, the number of occupied locations equals

$$ \alpha N. $$

Hence the amount of free space is

$$ (1-\alpha)N. $$

Algorithm $G$ allocates this free space among the $n$ stacks according to the formula

$$ \alpha_0=0.1\times \frac{\mathrm{SUM}}{n}, \qquad \beta=0.9\times \frac{\mathrm{SUM}}{\mathrm{INC}}, $$

where $\mathrm{SUM}$ is the unused space. Every stack therefore receives at least

$$ 0.1\frac{(1-\alpha)N}{n} $$

new vacant positions, regardless of its recent growth. Since $N\ge n^2$,

$$ 0.1\frac{(1-\alpha)N}{n} \ge 0.1(1-\alpha)n. $$

The next repacking can occur only when some stack exhausts its newly assigned reserve. Since every insertion increases the size of exactly one stack by one unit, at least

$$ c(1-\alpha)\frac{N}{n} $$

insertions must occur before the next overflow, where $c>0$ is an absolute constant. Deletions cannot hasten overflow, since they reduce stack sizes.

Let $\Delta$ denote the number of operations between these two repackings. Then

$$ \Delta = \Omega!\left( (1-\alpha)\frac{N}{n} \right). $$

The cost of the repacking itself is

$$ O(n+\alpha N). $$

We charge this cost uniformly to the $\Delta$ subsequent operations. The amortized repacking charge per operation is therefore

$$ O!\left( \frac{n+\alpha N} {(1-\alpha)N/n} \right). $$

Distributing the denominator gives

$$ O!\left( \frac{n^2}{(1-\alpha)N} + \frac{\alpha n}{1-\alpha} \right). $$

Since $N\ge n^2$,

$$ \frac{n^2}{(1-\alpha)N} \le \frac{1}{1-\alpha}. $$

Also,

$$ \frac{1}{1-\alpha} \le 1+\frac{\alpha}{1-\alpha}. $$

Hence the amortized repacking charge per operation is

$$ O!\left( 1+ n\frac{\alpha}{1-\alpha} \right). $$

Summing over all $m$ operations yields total repacking cost

$$ O\left( m+ n\sum_{k=1}^{m} \frac{\alpha_k}{1-\alpha_k} \right). $$

Adding the $O(m)$ ordinary insertion and deletion cost gives

$$ T(m) = O\left( m+ n\sum_{k=1}^{m} \frac{\alpha_k}{1-\alpha_k} \right). $$

This is the required estimate.

∎

Verification

Immediately after a repacking with occupancy fraction $\alpha$, the free space equals $(1-\alpha)N$. Algorithm $G$ guarantees that every stack receives at least a fixed positive fraction of the average free space, namely

$$ \Theta!\left(\frac{(1-\alpha)N}{n}\right). $$

Therefore no overflow can recur until at least that many insertions have occurred. Since a repacking costs $O(n+\alpha N)$, amortizing over the required number of subsequent insertions gives

$$ O!\left( \frac{n+\alpha N} {(1-\alpha)N/n} \right) = O!\left( 1+n\frac{\alpha}{1-\alpha} \right) $$

per operation. Summation over all operations reproduces the stated bound.

Notes

If the memory occupancy always satisfies $\alpha_k\le 0.9$, then

$$ \frac{\alpha_k}{1-\alpha_k} \le \frac{0.9}{0.1} = 9. $$

Hence

$$ n\sum_{k=1}^{m} \frac{\alpha_k}{1-\alpha_k} = O(mn), $$

and the amortized running time per operation becomes $O(n)$, independent of the total memory size $N$.