Content deleted Content added
m →Online selection algorithm: Fix use of parenthesis |
→Lower bounds: restore anchor externally linked from geeksforgeeks.org |
||
Line 71:
== Lower bounds ==
{{anchor|Tournament Algorithm}}
In ''[[The Art of Computer Programming]]'', [[Donald E. Knuth]] discussed a number of lower bounds for the number of comparisons required to locate the ''t'' smallest entries of an unorganized list of ''n'' items (using only comparisons). There is a trivial lower bound of ''n'' − 1 for the minimum or maximum entry. To see this, consider a tournament where each game represents one comparison. Since every player except the winner of the tournament must lose a game before we know the winner, we have a lower bound of ''n'' − 1 comparisons.
| |||