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:
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)
“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)