Access Restriction

Author Cunto, Walter ♦ Munro, J. Ian
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1989
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract It is shown that $\textit{n}$ + $\textit{k}$ - $\textit{O}(1)$ comparisons are necessary, on average, to find the $\textit{k}th$ smallest of $\textit{n}$ numbers $(\textit{k}$ ⪇ $\textit{n}/2).$ This lower bound matches the behavior of the technique of Floyd and Rivest to within a lower-order term. $7\textit{n}/4$ ± $\textit{o}(\textit{n})$ comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of $9\textit{n}/4$ ± $\textit{o}(\textit{n})$ and a lower bound of $2\textit{n}$ - $\textit{o}(\textit{n})$ are shown for the max-min-median problem.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1989-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 36
Issue Number 2
Page Count 10
Starting Page 270
Ending Page 279

Open content in new tab

   Open content in new tab
Source: ACM Digital Library