Computing Order Statistics
The problem of computing the kth smallest (or largest) element of a list is called the selection problem and is solved by a selection algorithm. Although this problem is difficult for very large lists, sophisticated selection algorithms have been created that can solve this problem in time proportional to the number of elements in the list, even if the list is totally unordered. If the data is stored in certain specialized data structures, this time can be brought down to O(log n). In many applications all order statistics are required, in which case a sorting algorithm can be used and the time taken is O(n log n).
Read more about this topic: Order Statistic
Famous quotes containing the words order and/or statistics:
“The fact that behavior is “normal,” or consistent with childhood development, does not necessarily make it desirable or acceptable...Undesirable impulses do not have to be embraces as something good in order to be accepted as normal. Neither does children’s behavior that is unacceptable have to be condemned as “bad,” in order to bring it under control.”
—Elaine Heffner (20th century)
“July 4. Statistics show that we lose more fools on this day than in all the other days of the year put together. This proves, by the number left in stock, that one Fourth of July per year is now inadequate, the country has grown so.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)