Content deleted Content added
Remove performance benefit claim |
Looks like some one cut and pasted with no link or useful infomration |
||
Line 111:
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 able to find the minimum (or maximum) element in constant time, while all other operations, including insertion, are O(log ''n''). More generally, a [[self-balancing binary search tree]] can easily be augmented to make it possible to both insert an element and find the ''k''th largest element in O(log ''n'') time
== Lower bounds ==
| |||