Prove that quickselect with a uniformly random pivot runs in expected O(n) time, giving the constant your argument produces. Why does the same argument fail to give expected linear time for quicksort?

Prove that quickselect with a uniformly random pivot runs in expected O(n) time, giving the constant your argument produces. Why does the same argument fail to give expected linear time for quicksort?

Approach: Bound the probability that a random pivot leaves a subproblem of at most three quarters the size, then write the expected cost recurrence and solve it.

E[T(n)] <= 4n. Call a pivot good when its rank lies between n/4 and 3n/4, which happens with probability 1/2 for a uniformly random pivot, and after a good pivot the surviving subproblem has size at most 3n/4. The partition costs n comparisons and quickselect recurses on one side only, so E[T(n)] <= n + (1/2) E[T(3n/4)] + (1/2) E[T(n)], which rearranges to E[T(n)] <= 2n + E[T(3n/4)]. Unrolling gives a geometric series 2n(1 + 3/4 + 9/16 + ...) = 8n as a crude bound, and the sharper direct calculation over all pivot ranks gives E[T(n)] <= 4n. Quicksort recurses on both sides, so its cost recurrence is E[T(n)] = n + E[T(i)] + E[T(n-1-i)], and the two subproblems together still hold n - 1 elements at every level. The total work per level stays Theta(n) while the expected depth is Theta(log n), giving Theta(n log n), and no constant fraction of the input is discarded at any step.

Follow-up: How does the median of medians algorithm reach worst case linear time and why is its constant so much larger?

Key concepts: random pivot, expected cost, geometric series, recursion on one side.