Reports
A Counting Approach to Lower Bounds for Selection Problems ; CU-CS-107-77 Public Deposited
https://scholar.colorado.edu/concern/reports/4b29b673r
- Abstract
- Lower bounds are derived on the number of comparisons to solve several well-known selection problems. Among the problems are: finding the t largest elements of a given set, in order (Wt); finding the s smallest and t largest elements, in order (Ws,t); and finding the tth largest element (Vt). The results follow from bounds for more general selection problmes, where an arbitrary partial order is given. The bounds for Wt and Vt generalize to the case where comparisons between linear functions of the input are allowed. The approach is to show a comparison tree for a selection problem contains a number of trees for smaller problems, thus establishing a lower bound on the number of leaves. An equivalent approach uses an adversary, based on a numerical “chaos” function that measures the number of unknown relations.
- Creator
- Date Issued
- 1977-08-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
aCountingApproachToLowerBoundsForSelectionProblemsCuC.pdf | 2019-12-21 | Public | Download |