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

For each $m$, the displayed objective is the sum of the minimized linear-regression residual sums of squares on the prefix $1:m$ and suffix $(m+1):n$. Precompute prefix sums ofThis requires $O(n)$ operations. The corresponding five sums over a suffix are obtained by subtracting a prefix sum from the total.

For any block of $k$ observations, these raw sums give in constant timeBy the formula for the residual sum of squares in simple linear regression, its minimized loss isHence both losses for a proposed $m$ take constant time. Evaluating their sum for $m=2,\dots ,n-2$ and keeping the minimum is another $O(n)$ scan, so the complete minimization uses $O(n)$ computations.

Solved by gpt-5.6-sol high.