Selection problems viaM-ary queries |
| |
| Authors: | Katia S. Guimarães William I. Gasarch Jim Purtilo |
| |
| Affiliation: | (1) Department of Computer Science, University of Maryland, 20742 College Park, MD, U.S.A.;(2) Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742 College Park, MD, U.S.A.;(3) Present address: Departamento de Informática, Universidade Federal de Pernambuco, 50739 Recife, PE, Brazil |
| |
| Abstract: | ![]()
It is well known that, for fixedk, to find thek-th largest ofn elementsn+(k?1)log2 n+Θ(1) comparisons are necessary and sufficient. But do the same bounds apply if we use a different type of query? We show that the arity of the queries is relevant. In particular, we present upper and lower bounds for finding the maximum using 3-ary or 4-ary Boolean (YES/NO answers) queries. We also study general (e.g.,max, sort) 3-ary queries, and show bounds for finding the maximum and the second largest. For sort queries we show matching upper and lower bounds. |
| |
| Keywords: | computational complexity selection problems lower bounds |
| 本文献已被 SpringerLink 等数据库收录！ |
|
