Worst case performance analysis of the two dimensional binary buddy system ∗

The worst case performance of the two dimensional binary buddy system is investigated. Tight lower bounds are given for two system performance measures, namely NETREQ and NETALLOC. Let the system size be 2 ⁿ × 2 ⁿ . It is shown that for any unrestricted saturating sequence S, we have NETREQ(S)≧4^n/2] + 4^{n/2] ? 1}+2^n/2]+l and NETALLOC(S)≧4^n/2] + 4^n/2]; for any allocation-only saturating sequence S, we have NETALLOC(S)≧4 ⁿ + 1 and NETREQ(S)≧4 ^n?1 + 2 ⁿ + 2.