Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / d / i / Solution

Sort the two dimension vectors separately into ascending order, $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$. Then return true exactly when $a_i<b_i$ for every $i$. Sorting costs $O(d\log d)$ and the coordinate comparisons cost $O(d)$.

Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose $a_k\ge b_k$ for some $k$. The $d-k+1$ dimensions $a_k,\dots ,a_d$ must all be assigned to strictly larger target dimensions. None of the first $k$ sorted target dimensions is large enough, leaving at most $d-k$ eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.