= Solution
With $X_1<\cdots<X_n$, it suffices to put the threshold between $X_m$ and $X_{m+1}$ for $m=1,\ldots,n-1$. Form the <prefix sum>[prefix sums]
$$
A_m=\sum_{i=1}^mY_i,
\qquad
B_m=\sum_{i=1}^mY_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.
Back to article page
