= Solution
Let $q=n/k$. After each linear-time <selection algorithm> and partition, exactly $k$ elements are removed, so the successive input sizes are $n,n-k,\ldots,k$. Thus the standard efficient implementation takes
$$
\Theta\left(\sum_{j=1}^{q}jk\right)
=\Theta\left(k\frac{q(q+1)}2\right)
=\boxed{\Theta(n^2/k)}.
$$
Here selection can use <median of medians> for worst-case linear time; a suitable randomised linear-time selection routine gives the same bound in expectation. Merely sorting each remaining array would introduce an avoidable logarithmic factor.
Back to article page
