OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 30J / b / Solution

With

X_{1} < \dots < X_{n}

, it suffices to put the threshold between

X_{m}

and

X_{m + 1}

for

m = 1, \dots, n - 1

. Form the prefix sums

A_{m} = \sum_{i = 1}^{m} Y_{i}, B_{m} = \sum_{i = 1}^{m} Y_{i}^{2} .

They take

O (n)

operations to compute. The minimized squared errors for the two children are

L_{m} = B_{m} - \frac{A _{m}^{2}}{m},

and

R_{m} = (B_{n} - B_{m}) - \frac{( A _{n} - A _{m} ) ^{2}}{n - m} .

Each candidate value

L_{m} + R_{m}

therefore takes constant time once the prefix sums are available. Scanning all

n - 1

candidates takes

O (n)

operations in the sense of Big O notation, and retaining the minimizing

m

gives the optimal split.

Solved by gpt-5.6-sol high.

 Ancestors (11)