Chapter 9 Medians and Order Statistics
The ith order statistic of a set of n elements is the ith smallest element.
- the minimum of a set of elements is the first order statistic (i = 1).
- the maximum is the nth order statistic (i = n).
- A median, informally, is the "halfway point" of the set.
For convenience, consider the problem of selecting the ith order statistic from a set of n distinct numbers.
We can solve the selection problem in O(nlgn) time, since we can sort the numbers and then simply index the ith element in the output array. Can we do it better?
9.1 Mninum and maximum
\[
MINIMUM(A)\\
1 min = A[1]\\
2 for i = 2 to A.length\\
3 \quad if min > A[i]\\
4 \quad \quad min = A[i]\\
5 \quad return min
\]
n - 1 comparisons