The ith order statistic of a set of n elements is the ith smallest element. For example, the minimum of a set of elements is the first order statistic (i = 1), and the maximum is the nth order statistic (i = n). The asymptotic running time of the simple problem of finding a minimum or maximum is Θ(n). Yet select the ith smallest element appears more difficult but it also only need Θ(n) time.
Continue reading “Notes of Introduction to Algorithm(Order Statistics)”