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:
“I do not know if you remember the tale of the girl who saves the ship under mutiny by sitting on the powder barrel with her lighted torch ... and all the time knowing that it is empty? This has seemed to me a charming image of the women of my time. There they were, keeping the world in order ... by sitting on the mystery of life, and knowing themselves that there was no mystery.”
—Isak Dinesen [Karen Blixen] (1885–1962)
“He uses statistics as a drunken man uses lamp-posts—for support rather than illumination.”
—Andrew Lang (1844–1912)