Content deleted Content added
== Using data structures to select in sublinear time == |
|||
Line 113:
Given an unorganized list of data, linear time (Ω(''n'')) is required to find the minimum element, because we have to examine every element (otherwise, we might miss it.) If we organize the list, for example by keeping it sorted at all times, then selecting the ''k''th largest element is trivial, but then insertion requires linear time, as do other operations such as combining two lists.
When only the minimum (or maximum) is needed, a better approach is to use a [[priority queue]], which is typically able to find the minimum element in constant time, while all other operations, including insertion, are O(log ''n'')
== References ==
| |||