= Solution
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^2N+\cdots$, giving \b[$\Theta(N)$] time.
Repeatedly choosing an extreme pivot while searching toward the other end retains lengths $N-1,N-2,\ldots$, giving \b[$\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.
Back to article page
