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:
“Children need people in order to become human.... It is primarily through observing, playing, and working with others older and younger than himself that a child discovers both what he can do and who he can become—that he develops both his ability and his identity.... Hence to relegate children to a world of their own is to deprive them of their humanity, and ourselves as well.”
—Urie Bronfenbrenner (b. 1917)
“We ask for no statistics of the killed,
For nothing political impinges on
This single casualty, or all those gone,
Missing or healing, sinking or dispersed,
Hundreds of thousands counted, millions lost.”
—Karl Shapiro (b. 1913)