Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8 / c / 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,\dots ,k$. Thus the standard efficient implementation takesHere 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.