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 sentimentalist ... exclaims: “Would you have a woman step down from her pedestal in order to enter practical life?” Yes! A thousand times, yes! If we can really find, after a careful search, any women mounted upon pedestals, we should willingly ask them to step down in order that they may meet and help to uplift their sisters. Freedom and justice for all are infinitely more to be desired than pedestals for a few.”
—Bertha Honore Potter Palmer (1849–1918)
“O for a man who is a man, and, as my neighbor says, has a bone in his back which you cannot pass your hand through! Our statistics are at fault: the population has been returned too large. How many men are there to a square thousand miles in this country? Hardly one.”
—Henry David Thoreau (1817–1862)