Lower Bounds
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.
The story becomes more complex for other indexes. We define as the minimum number of comparisons required to find the t smallest values. Knuth references a paper published by S. S. Kislitsyn, which shows an upper bound on this value:
This bound is achievable for t=2 but better, more complex bounds are known for larger t.
Read more about this topic: Selection Algorithm
Famous quotes containing the word bounds:
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)