 Solution

For the active set $A_k$, maintainThe initial $n\times n$ matrix inverse costs $O(n^3)$. At step $k$, compute $v_k=M_k^{-1}Y$ in $O(n^2)$ operations and all active ridge coefficients $X_{A_k}^T{v}_k$ in $O(|A_k|n)$ operations; their smallest absolute value determines $j_k$.

After deleting $j_k$,Part b ensures that the denominator in the Sherman–Morrison formula is positive, and the rank-one downdatecosts $O(n^2)$. Summing over the $p$ steps givesSince $p\ge n$, both earlier terms are bounded by $O(p^{2}n)$, proving the claimed computational complexity within computational complexity theory.