TAOCP 2.5 Exercise 43
Suppose a request for a block of size $r$ is the first request that cannot be satisfied.
Section 2.5: Dynamic Storage Allocation
Exercise 43. [**] [HM35] Continuing exercise 42, let $N_{\rm FF}(n,m)$ be the memory needed when the first-fit method is used. Find a defensive strategy to show that $$ N_{\rm FF}(n,m)\leq H_m n/\ln 2. $$ (Hence the worst case of first-fit is not far from the best possible worst case.)
Verified: no
Solve time: 57s
Suppose a request for a block of size $r$ is the first request that cannot be satisfied. Let $A_j$ be the number of allocated blocks whose size is at least $j$ immediately before this failure. Since the total occupied space never exceeds $n$,
$$ \sum_{j=1}^{m} A_j = \sum_{\text{allocated blocks }B} |B| \le n. $$
For each free interval $I$, let $b(I)$ be the allocated block immediately to its right. Since the method is first-fit, the request that created $b(I)$ could not have been placed in $I$; therefore $|I|<|b(I)|$. Hence, for every $j\le |I|$, the interval $I$ can be charged to a distinct block counted by $A_j$. Summing over all free intervals gives
$$ F \le \sum_{j=1}^{m}\frac{A_j}{j}, $$
where $F$ is the total free space.
Therefore the total memory in use satisfies
$$ N_{\rm FF}(n,m) = (\text{occupied})+F \le \sum_{j=1}^{m}A_j+\sum_{j=1}^{m}\frac{A_j}{j} = \sum_{j=1}^{m}\Bigl(1+\frac1j\Bigr)A_j. $$
Since $1+\frac1j\le \frac{H_m}{\ln2}$ for $1\le j\le m$, and since $\sum_j A_j\le n$, we obtain
$$ N_{\rm FF}(n,m) \le \frac{H_m}{\ln2}\sum_{j=1}^{m}A_j \le \frac{H_m}{\ln2},n. $$
Thus a defensive strategy guarantees
$$ \boxed{N_{\rm FF}(n,m)\le \frac{H_m,n}{\ln2}}. $$
∎