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:
“A wise man should order his interests, and set them all in their proper places. This order is often troubled by greed, which puts us upon pursuing so many things at once that, in eagerness for matters of less consideration, we grasp at trifles, and let go things of greater value.”
—François, Duc De La Rochefoucauld (1613–1680)
“Maybe a nation that consumes as much booze and dope as we do and has our kind of divorce statistics should pipe down about “character issues.” Either that or just go ahead and determine the presidency with three-legged races and pie-eating contests. It would make better TV.”
—P.J. (Patrick Jake)