Let S be a set of n elements that allows all possible total ordering and on which a total order exists that is initially not known. The problem of determining the t largest elements of S using binary comparisons between elements of S is the set-partitioning problem. In this paper we establish a new lower bound on the number of comparisons required for the set-partitioning problem. For sufficiently large n, our lower bound improves on all previous lower bounds for this problem for almost all values of t. Our technique is based on estimating the number of leaves of a decision tree, say T, for the problem. Let P denote the set of total orderings allowed on S. Let $P'_i ,P'_2 , \cdots ,P'_m $ be a partition of P such that the set of leaves of T corresponding to $P'_i $ is disjoint from those corresponding to $P'_j $ whenever $i \ne j$. We determine subsets $P_1 ,P_2 , \cdots ,P_r $ of P and an integer k, such that for each i, $1 \leqq i \leqq m$, $P'_i \cap P_j \ne \emptyset $ holds for at most k distinct $P_j $’s. For each subset $P_j $, $1 \leqq j \leqq r$, we establish a lower bound, say $t_j $, on the number of leaves of a decision tree for the set-partitioning problem when S is restricted to a total order from $P_j $. Then T has at least $\sum\nolimits_{j = 1}^r {{{t_j } / k}} $ leaves.

Article Free Access Share on Finding the median requires 2n comparisons Authors: S W Bent Computer Science Department, University of Wisconsin-Madison, 1210 West Dayton St., Madsion, Wisconsin Computer Science Department, University of Wisconsin-Madison, 1210 West Dayton St., Madsion, WisconsinSearch about this author , J W John Computer Science Department, University of Wisconsin-Madison, 1210 West Dayton St., Madsion, Wisconsin Computer Science Department, University of Wisconsin-Madison, 1210 West Dayton St., Madsion, WisconsinView Profile Authors Info & Claims STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingDecember 1985 Pages 213–216https://doi.org/10.1145/22145.22169Online:01 December 1985Publication History 25citation726DownloadsMetricsTotal Citations25Total Downloads726Last 12 Months20Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF