Thumbnail
Access Restriction
Subscribed

Author Yap, Chee K.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Selection problem ♦ Worst-case analysis ♦ Algorithms ♦ Upper bounds ♦ Concrete computational complexity ♦ Comparison problems
Abstract The worst-case, minimum number of comparisons complexity Vi(n) of the i-th selection problem is considered. A new upper bound for Vi(n) improves the bound given by the standard Hadian-Sobel algorithm by a generalization of the Kirkpatrick-Hadian-Sobel algorithm, and extends Kirkpatrick's method to a much wider range of application. This generalization compares favorably with a recent algorithm by Hyafil.
Description Affiliation: Yale Univ., New Haven, CT (Yap, Chee K.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 19
Issue Number 9
Page Count 8
Starting Page 501
Ending Page 508


Open content in new tab

   Open content in new tab
Source: ACM Digital Library