 Solution

ID: 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} \leq \dots \leq a_{d}

and

b_{1} \leq \dots \leq b_{d}

. Then return true exactly when $a_{i} < b_{i}$ for every $i$ . Sorting costs

O (d lo g 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} \geq b_{k}

for some

k

. The

d - k + 1

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.

 New to topics? Read the docs here!