caa a22 4500 469033916 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF01272077 doi (NATIONALLICENCE)springer-10.1007/BF01272077 Selection problems via M -ary queries [Elektronische Daten] [Katia Guimarães, William Gasarch, Jim Purtilo] 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. Birkhäuser Verlag, 1992 computational complexity nationallicence selection problems nationallicence lower bounds nationallicence 68Q05 nationallicence 68Q25 nationallicence Guimarães Katia Department of Computer Science, University of Maryland, 20742, College Park, MD, U.S.A. aut Gasarch William Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, U.S.A. aut Purtilo Jim Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, U.S.A. aut computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 256-276 1016-3328 2:3<256 1992 2 37 https://doi.org/10.1007/BF01272077 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01272077 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Guimarães Katia Department of Computer Science, University of Maryland, 20742, College Park, MD, U.S.A aut NATIONALLICENCE 700 1- Gasarch William Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, U.S.A aut NATIONALLICENCE 700 1- Purtilo Jim Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742, College Park, MD, U.S.A aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/3(1992-09-01), 256-276 1016-3328 2:3<256 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer