On the Average-Case Complexity of Selecting the kth Best

DOI10.1137/0211034zbMath0486.68069OpenAlexW2152904264MaRDI QIDQ3947142

Andrew Chi-Chih Yao, F. Frances Yao

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4c0e0cbe9b40f98da6b5322d06f12e1ffcd81926

zbMATH Keywords

binary treeselectiondecision treeminimum average number of pairwise comparisons

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Related Items

Select with Groups of 3 or 4, On partial sorting in restricted rounds, A selectable sloppy heap, Selection Algorithms with Small Groups, Some Monotonicity Properties of Partial Orders