Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 2 / d

For an active segment of length $s$, partitioning takes $\Theta (s)$ comparisons. If pivot choice costs at most linear time and always leaves at most an $\alpha <1$ fraction on the searched side, the total is bounded by the geometric series $N+\alpha N+{\alpha }^{2}N+\cdots$, giving $\Theta (N)$ time.

Repeatedly choosing an extreme pivot while searching toward the other end retains lengths $N-1,N-2,\dots$, giving $\Theta (N^2)$ worst-case time. The equality interval makes an all-equal input finish in one partition. Independent uniform random pivots give expected linear time for duplicate-aware Quickselect, but this is not a deterministic worst-case guarantee. More expensive pivot selection must be included in the cost rather than hidden inside the partition bound.