On Lower Bounds for Selecting the Median.
We present a reformulation of the 2n+o(n) lower bound of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 213--216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function.  Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it.  We use the new formulation to show that any  pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing $\lfloor n/2\rfloor$ disjoint pairs of elements must perform, in the worst case, at least 2.01 n comparisons. This provides strong evidence that selecting the median requires at least cn+o(n) comparisons for some c> 2.
Introduction
. Sorting and selection problems have received extensive attention
by computer scientists and mathematicians for a long time. Comparison based
algorithms for solving these problems work by performing pairwise comparisons between
the elements until the relative order of all elements is known, in the case of
or until the i-th largest element among the n input elements is found, in the
case of selection.
Sorting in a comparison based computational model is quite well understood. Any
deterministic algorithm can be modeled by a decision tree in which all internal nodes
represent a comparison between two elements; every leaf represents a result of the
computation. Since there must be at least as many leaves in the decision tree as there
are possible re-orderings of n elements, all algorithms that sort n elements use at least
dlog n!e  n log n n log e comparisons in the worst
case. (All logarithms in this paper are base 2 logarithms.) The best known sorting
method, called merge insertion by Knuth [9], is due to Lester Ford Jr. and Selmer
Johnson [7]. It sorts n elements using at most n log n 1:33n
Thus, the gap between the upper and lower bounds is very narrow in that the error
in the second order term is bounded by 0:11n.
The problem of nding the median is the special case of selecting the i-th largest
in an ordered set of n elements, when Although much eort has been put
into nding the exact number of required comparisons, there is still an annoying gap
between the best upper and lower bounds currently known.
Knowing how to sort, we could select the median by rst sorting, and then selecting
the middle-most element; it is quite evident that we could do better, but how much
better? This question received a somewhat surprising answer when Blum et al. [3]
showed, in 1973, how to determine the median in linear time using at most 5:43n
comparisons. This result was improved upon in 1976 when Schnhage, Paterson, and
Pippinger [13] presented an algorithm that uses only 3n
School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv
University, Tel Aviv 69978, Israel. E-mail: dorit@checkpoint.com and zwick@post.tau.ac.il.
y Department of Numerical Analysis and Computing Science, Royal Institute of Technology, 100 44
Stockholm, Sweden. E-mail: fjohanh,staffanug@nada.kth.se.
D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
main invention was the use of factories which mass-produce certain partial orders
that can be easily merged with each other.
This remained the best algorithm for almost 20 years, until Dor and Zwick [5]
pushed down the number of comparisons a little bit further to 2:95n + o(n) by adding
green factories that recycle debris from the merging process used in the algorithm
of [13].
The rst non-trivial lower bound for the problem was also presented, in 1973, by
Blum et al. [3] using an adversary argument. Their 1:5n lower bound was subsequently
improved to 1:75n + o(n) by Pratt and Yao [12] in 1973. Then Yap [14], and later
Munro and Poblete [10], improved it to 38
43 n+O(1), respectively. The
proofs of these last two bounds are long and complicated.
In 1979, Fussenegger and Gabow [8] proved a 1:5n + o(n) lower bound for the
median using a new proof technique. Bent and John [2] used the same basic ideas
when they gave, in 1985, a short proof that improved the lower bound to 2n
which is currently the best available. Thus, the uncertainty in the coe-cient of n is
larger for nding the median than it is for sorting, even though the linear term is the
second order term in the case of sorting.
Since our methods are based on the proof by Bent and John, let us describe it in
some detail. Given the decision tree of a comparison based algorithm, they invented
a method to prune it that yields a collection of pruned trees. Then, lower bounds
for the number of pruned trees and for their number of leaves are obtained. A nal
argument saying that the leaves of the pruned trees are almost disjoint then gives a
lower bound for the size of the decision tree.
In Section 2 we reformulate the proof by Bent and John by assigning weights
to each node in the decision tree. The weight of a node v corresponds to the total
number of leaves in subtrees with root v in all pruned trees where v occurs in the
proof by Bent and John. The weight of the root is approximately 2 2n ; we show that
every node v in the decision tree has a child whose weight is at least half the weight
of v, and that the weights of all the leaves are small.
When the proof is formulated in this way, it becomes more transparent, and one
can more easily study individual comparisons, to rule out some as being bad from the
algorithm's point of view.
For many problems, such as nding the maximal or the minimal element of an
ordered set, and nding the maximal and minimal element of an ordered set, there
are optimal algorithms that start by making bn=2c pairwise comparisons between
singleton elements. We refer to algorithms that start in this way as being pair-
forming. It has been discussed whether there are optimal pair-forming algorithms for
all partial orders, and in particular this question was posed as an open problem by
Aigner [1]. Some examples were then found by Chen [4], showing that pair-forming
algorithms are not always optimal.
It is interesting to note that the algorithms in [5] and [13] are both pair-forming.
It is still an open problem whether there are optimal pair-forming algorithms for
nding the median.
In Section 3 we use our new approach to prove that any pair-forming algorithm
uses at least 2:01227n comparisons to nd the median.
Dor and Zwick [6] have recently been able to extend the ideas described here and
obtain a (2+)n lower bound, for some tiny  > 0, on the number of comparisons
performed, in the worst case, by any median selection algorithm.
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 3
2. Bent and John revisited. Bent and John [2] proved that 2n + o(n) comparisons
are required for selecting the median. Their result, in fact, is more general
and provides a lower bound for the number of comparisons required for selecting the
i-th largest element, for any 1  i  n. We concentrate here on median selection
although our results, like those of Bent and John, can be extended to general i.
Although the proof given by Bent and John is relatively short and simple, we here
present a reformulation. There are two reasons for this: the rst is that the proof
gets more transparent; the second is that this formulation makes it easier to study
the eect of individual comparisons.
Theorem 2.1 (Bent and John [2]). Finding the median requires 2n comparisons

Proof.
Any deterministic algorithm for nding the median can be represented by a decision
tree T , in which each internal node v is labeled by a comparison a : b. The
two children of such a node, v a<b and v a>b , represent the outcomes a < b and a > b,
respectively. We assume that decision trees do not contain redundant comparisions
between elements whose relative order has already been established.
We consider a universe U containing n elements. For every node v in T and
subset C of U we make the following denitions:
every comparison a : b above v
with b 2 C had outcome a > b
every comparison a : b above v
with b 2 C had outcome a < b
Before we proceed with the proof that selecting the median requires 2n
parisons, we present a proof of a somewhat weaker result. We assume that U contains
show that selecting the two middlemost elements requires
comparisons. The proof in this case is slightly simpler, yet it demonstrates
the main ideas used in the proof of the theorem.
We dene a weight function on the nodes of T . This weight function satises the
following three properties: (i) the weight of the root is 2 2n+o(n) . (ii) each internal
node v has a child whose weight is at least half the weight of v. (iii) the weight of
each leaf is small.
For every node v in the decision tree, we keep track of subsets A of size m which
may contain the m largest elements with respect to the comparisons already made.
Let A(v) contain all such sets which are called upper half compatible with v. The As
are assigned weights which estimate how far from a solution the algorithm is, assuming
that the elements in A are the m largest. The weight of every A 2 A(v) is dened as
and the weight of a node v is dened as
The superscript 1 in w 1
(A) is used as we shall shortly have to dene a second weight
function w 2
(B).
4 D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
case w 1
a 2 A b 2 A 1
a 2 A b 2
a 2
a 2

Table
The weight of a set A 2 A(v) in the children of a node v, relative to its weight in v.
In the root r of T , all subsets of size m of U are upper half compatible with r so
that
. Also, each A 2 A(r) has weight 2 2m , and we nd, as promised,
that
2m
Consider the weight w 1
(A) of a set A 2 A(v) at a node v labeled by the comparison
b. What are the weights of A in v's children? This depends on which of the
elements a and b belongs to A (and on which of them is minimal in A or maximal
in
A). The four possible cases are considered in Table 2.1. The weights given there are
relative to the weight w 1
of A at v. A zero indicates that A is no longer compatible
with this child and thus does not contribute to its weight. The weight w 1
va<b (A), when
example, is 1
(A), and is w 1
(A), otherwise. As can be
seen, v always has at least one child in which the weight of A is at least half its weight
at v. Furthermore, in each one of the four cases, w 1
(A).
Each leaf v of the decision tree corresponds to a state of the algorithm in which
the two middlemost elements were found. There is therefore only one set A left in
A(v). Since we have identied the minimum element in A and the maximum element
in
A, we get that w 1
4. So, if we follow a path from the root of the tree and
repeatedly descend to the child with the largest weight, we will, when we eventually
reach a leaf, have performed at least 2n
We now prove that selecting the median also requires at least 2n
isons. To make the median well dened we assume that 1. The problem
that arises in the above argument is that the weights of the leaves in T , when the
selection of the median, and not the two middlemost elements, is considered, are not
necessarily small enough: it is possible to know the median without knowing any relations
between elements in
A (which now contains m 1 elements); this is remedied
as follows.
In a node v where the algorithm is close to determining the minimum element
in A, we essentially force it to determine the largest element in
A instead. This is done
by moving an element a 0 out of A and creating a set
g. This set is lower
half compatible with v and the median is the maximum element in B. By a suitable
choice of a 0 , most of max v (
is in max v (B). A set B is lower half compatible with v
may contain the m smallest elements in U . We keep track of Bs in
the multiset B(v).
For the root r of T , we let A(r) contain all subsets of size m of U as before, and
let B(r) be empty. We exchange some As for Bs as the algorithm proceeds. The
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 5
case
a 2
a 2

Table
The weight of a set B 2 B(v) in the children of a node v, relative to its weight in v.
weight of a set B is dened as
The weight of B estimates how far the algorithm is from a solution, assuming that
the elements in B are the m smallest elements. The weight of a node v is now dened
to be
In the beginning of an algorithm (in the upper part of the decision tree), the weight
of a node is still the sum of the weights of all As, and therefore
We now dene A(v) and B(v) for the rest of T more exactly. For any node v in T ,
except the root, simply copy A(v) and B(v) from the parent node and remove all sets
that are not upper or lower half compatible with v, respectively. We ensure that the
weight of every leaf is small by doing the following: If, for some A 2 A(v) we have
ne, we select an element a 0 2 min v (A) which has been compared to
the fewest number of elements in
A; we then remove the set A from A(v) and add the
set
to B(v).
Note that at the root, jmin r and that this quantity
decreases by at most one for each comparison until a leaf is reached. In a leaf v the
median is known; thus, A(v) is empty.
Lemma 2.2. Let A(v) and B(v) be dened by the rules described above. Then,
every internal node v (labeled a : b) in T has a child with at least half the weight of v,
i.e., w(v a<b )  w(v)=2 or w(v a>b )  w(v)=2.
Proof.

Table

2.1 gives the weights of a set A 2 A(v) at v's children, relative to the
weight
of A at v. Similarly, Table 2.2 gives the weights of a set B 2 B(v) in v's
children, relative to the weight w 2
v (v) of B at v. As w 1
v (B), for every A 2 A(v) and B 2 B(v), all that remains to
be checked is that the weight does not decrease when a lower half compatible set B
replaces an upper half compatible set A. This is covered by Lemma 2.3.
Lemma 2.3. If A is removed from A(v) and B is added in its place to B(v), and
if fewer than 4n comparisons have been performed on the path from the root to v, then
(A).
Proof. A set A 2 A(v) is replaced by a set
only when
ne. The element a 0 , in such a case, is an element of min v (A) that
has been compared to the fewest number of elements in
A. If a 0 was compared to at
least 2
n elements in
A, we get that each element of min v (A) was compared to at
6 D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
least 2
n elements in
A, and at least 4n comparisons have been performed on the path
from the root to v, a contradiction. We get therefore that a 0 was compared to fewer
than 2
n elements of
A and thus jmax v (B)j > jmax v (
n. As a consequence,
we get that 4
A)j and thus 2 4
as required.
We now know that the weight of the root is large, and that the weight does not
decrease too fast; what remains to be shown is that the weights of the leaves are
relatively small. This is established in the following lemma.
Lemma 2.4. For a leaf v (in which the median is known), w(v)  2m2 4
Proof. Clearly, the only sets compatible with a leaf of T are the set A containing
the m largest elements, and the set B containing the m smallest elements. Since
we get that w 2
Since there are exactly m elements that can be removed from B to obtain a
corresponding
A, there can be at most m copies of B in B(v).
Let T be a comparison tree that corresponds to a median nding algorithm. If
the height of T is at least 4n, we are done. Otherwise, by starting at the root and
repeatedly descending to a child whose weight is at least half the weight of its parent,
we trace a path whose length is at least 2n + o(n) and Theorem 2.1 follows.
Let us see how the current formalism gives room for improvement that did not
exist in the original proof. The 2n lower bound is obtained by showing that
each node v in a decision tree T that corresponds to a median nding algorithm has
a child whose weight is at least half the weight of v. Consider the nodes v
along the path obtained by starting at the root of T and repeatedly descending to the
child with the larger weight, until a leaf is reached. If we could show that su-ciently
many nodes on this path have weights strictly larger than half the weights of their
parents, we would obtain an improved lower bound for median selection. If w(v i then the length of this path, and therefore the
depth of T , is at least 2n
3. An improved lower bound for pair-forming algorithms. Let v be a
node of a comparison tree. An element x is a singleton at v if it was not compared
above v with any other element. Two elements x and y form a pair at v if the
elements x and y were compared to each other above v, but neither of them was
compared to any other element.
A pair-forming algorithm is an algorithm that starts by constructing
By concentrating on comparisons that involve elements that are part of
pairs, we obtain a better lower bound for pair-forming algorithms.
Theorem 3.1. A pair-forming algorithm for nding the median must perform,
in the worst case, at least 2:00691n
Proof.
It is easy to see that a comparison involving two singletons can be delayed until
just before one of them is to be compared for the second time. We can therefore
restrict our attention to comparison trees in which the partial order corresponding
to each node contains at most two pairs. Allowing only one pair is not enough as
algorithms should be allowed to construct two pairs fa; bg and fa
compare an element from fa; bg with an element from fa g.
We focus our attention on nodes in the decision tree in which an element of a
pair is compared for the second time and in which the number of non-singletons is at
most m, for some  < 1. If v is a node in which the number of non-singletons is at
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 7
r
a
r
a
r
a
r
r
a
r
a
r
a
r
A
A
Fig. 3.1. The six possible ways that a, b, and c may be divided between A and
A. Note that c
is not necessarily a singleton element; it may be part of a larger partial order.
most m, for some  < 1, then B(v) is empty and thus
we do not have to consider Table 2.2 for the rest of the section.
Recall that A(v) denotes the collection of subsets of U size m that are upper half
compatible with v. If H;L  U are subsets of U , of arbitrary size, we let
Ag:
We let wH=L (v) be the contribution of the sets of AH=L (v) to the weight of v, i.e.,
For brevity, we write A
(v) for A fh1 ;:::;h r g=fl1 ;:::;l s g (v) and w
(v)
for w fh1 ;:::;h r g=fl1 ;:::;l s g (v).
Before proceeding, we describe the intuition that lies behind the rest of the proof.
Consider Table 2.1 from the last section. If, in a node v of the decision tree, the
two cases a 2 A; b 2
A and a 2
are not equally likely, or more precisely,
if the contributions w a=b (v) and w b=a (v) of these two cases to the total weight of v
are not equal, there must be at least one child of v whose weight is greater than half
the weight of v. The di-culty in improving the lower bound of Bent and John lies
therefore at nodes in which the the contributions of the two cases a 2 A; b 2
A and
a 2
are almost equal. This fact is not so easily seen when looking at the
original proof given in [2].
Suppose now that v is a node in which an element a of a pair fa; bg is compared
with an arbitrary element c and that the number of non-singletons in v is at most
m. We assume, without loss of generality, that a > b. The weights of a set A 2 A(v)
in v's children depend on which of the elements a, b, and c belongs to A, and on
whether c is minimal in A or maximal in
A. The six possible ways of dividing the
elements a, b, and c between A and
A are shown in Figure 3.1. The weights of the
set A in v's children, relative to the weight w 1
of A at v, in each one of these six
cases are given in Table 3.1. Table 3.1 is similar to Table 2.1 of the previous section,
with c playing the role of b. There is one important dierence, however. If a; b; c 2 A,
as in the rst row of Table 3.1, then the weight of A in v a>c is equal to the weight of A
in v. The weight is not halved, as may be the case in the rst row of Table 2.1. If the
contribution w abc= (v) of the case a; b; c 2 A to the weight of v is not negligible, there
must again be at least one child of v whose weight is greater than half the weight of v.
The improved lower bound is obtained by showing that if the contributions of
the cases a 2 A, b 2
A and a 2
are roughly equal, and if most elements in
the partial order are singletons, then the contribution of the case a; b; c 2 A is non-
negligible. The larger the number of singletons in the partial order, the larger is the
relative contribution of the weight w abc= (v) to the weight w(v) of v. Thus, whenever
8 D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
case w 1
a 2 A b 2
a 2 A b 2 A c 2
a 2 A b 2
a 2
A 11

Table
The weight of a set A 2 A(v) in the children of a node v, relative to its weight in v, when the
element a of a pair a > b is compared with an arbitrary element c.
an element of a pair is compared for the second time, we make a small gain. The
above intuition is made precise in the following lemma:
Lemma 3.2. If v is a node in which an element a of a pair a > b is compared
with an element c, and if the number of singletons in v is at least m+ 2 p
(w a=c (v) w c=a (v)
Proof. Both inequalities follow easily by considering the entries in Table 3.1. To
obtain the second inequality, for example, note that w(v a>c
As w c=ab
w a=c (v), the second inequality follows.
It is worth pointing out that in Table 3.1 and in Lemma 3.2, we only need to
assume that a > b; we do not use the stronger condition that a > b is a pair. This
stronger condition is crucial however in the sequel, especially in Lemma 3.4.
To make use of Lemma 3.2 we need bounds on the relative contributions of the
dierent cases. The following lemma is a useful tool for determining such bounds.
Lemma 3.3. Let E) be a bipartite graph. Let - 1 and - 2 be the minimal
degree of the vertices of V 1 and V 2 , respectively. Let  1 and  2 be the maximal degree
of the vertices of V 1 and V 2 , respectively. Assume that a positive weight function w is
dened on the vertices of G such that w(v 1
and (v
r
Proof. Let denote the two vertices connected by the
edge e. We then have
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 9
The other inequality follows by exchanging the roles of V 1 and V 2 .
Using Lemma 3.3 we obtain the following basic inequalities.
Lemma 3.4. If v is a node in which a > b is a pair and the number of non-
singletons in v is at most m, then2
Each one of these inequalities relates a weight, such as w abc= (v), to a weight, such
as w ac=b (v), obtained by moving one of the elements of the pair a > b from A to
A.
In each inequality we 'lose' a factor of 1 . When the elements a and b are joined
together a factor of 2 is introduced. When the elements a and b are separated, a
factor of 1is introduced.
Proof. We present a proof of the inequality w abc= (v)  1
(v). The proof
of all the other inequalities is almost identical.
Construct a bipartite graph E) whose vertex sets are
(v). Dene an edge
A ac=b (v) if and only if there is a singleton d 2
A 1 such that A
Suppose that is such an edge. As a 62 min v
other elements are extremal with respect to A 1 if and only if they are extremal with
respect to A 2 (note that b 2 min v
A 2 )), we get that w 1
For every set A of size m, the number of singletons in A is at least (1 )m and
at most m. We get therefore that the minimal degrees of the vertices of V 1 and V 2
are and the maximal degrees of V 1 and V 2 are  1 ;  2  m. The
inequality w abc= (v)  1
therefore follows from Lemma 3.3.
Using these basic inequalities we obtain:
Lemma 3.5. If v is a node in which a > b is a pair and the number of non-
singletons is at most m, for some  < 1, then
Proof. We present the proof of the rst inequality. The proof of the other two
inequalities is similar. Using inequalities from Lemma 3.4 we get that
and the rst inequality follows.
D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
We are now ready to show that if v is a node in which an element of a pair is
compared for the second time, then v has a child whose weight is greater than half
the weight of v. Combining Lemma 3.2 and Lemma 3.5, we get that2 (w(v a<c
w(v)
As a consequence, we get that
The coe-cient of w(v), on the right hand side, is minimized when the two expressions
whose maximum is taken are equal. This happens when
. Plugging
this value of  into the two expressions, we get that
where
It is easy to check that f 1 () > 0 for  < 1.
A pair-forming comparison is a comparison in which two singletons are compared
to form a pair. A pair-touching comparison is a comparison in which an element
of a pair is compared for the second time. In a pair-forming algorithm, the number
of singletons is decreased only by pair-forming comparisons. Each pair-forming
comparison decreases the number of singletons by exactly two. As explained above,
pair-forming comparisons can always be delayed so that a pair-forming comparison
immediately followed by a comparison that touches the pair fa; bg, or by a
pair-forming comparison a then by a comparison that touches both pairs
g.
Consider again the path traced from the root by repeatedly descending to the
child with the larger weight. As a consequence of the above discussion, we get that
when the i-th pair-touching comparison along this path is performed, the number
of non-singletons in the partial order is at most 4i. It follows therefore from the
remark made at the end of the previous section that the depth of the comparison tree
corresponding to any pair-forming algorithm is at least
log
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 11
r
a
r
a
r
a
r
r
a
r
a
r
a
r
r
a
r
a
r
a
r
r c
r d
r c
r d
r c
r d
r c
r d
r c
r d
r c
r d
r c
r d
A
A
Fig. 3.2. The nine possible ways that a, b, c, and d may be divided between A and
A.
case w 1

Table
The weight of a set A 2 A(v) in the children of a node v, relative to its weight in v, when the
element a of a pair a > b is compared with an element of a pair c > d.
This completes the proof of Theorem 3.1.
The worst case in the proof above is obtained when the algorithm converts all the
elements into quartets . A quartet is a partial order obtained by comparing elements
contained in two disjoint pairs. In the proof above, we analyzed cases in which an
element a of a pair a > b is compared with an arbitrary element c. If the element c is
also part of a pair, a tighter analysis is possible. By performing this anaylsis we can
improve Theorem 3.1.
Theorem 3.6. A pair-forming algorithm for nding the median must perform,
in the worst case, at least 2:01227n
Proof. Consider comparisons in which the element from a pair a > b is compared
with an element of a pair c > d. The nine possible ways of dividing the elements a,
b, c, and d among A and
A are depicted in Figure 3.2. We may assume, without loss
of generality, that the element a is compared with either c or with d.
Let v be a node of the comparison tree in which a > b and c > d are pairs and
which one of the comparions a : c or a : d is performed. Let A 2 A(v). The weights
of a set A in v's children, relative to the weight w 1
of A at v, in each one of these
nine cases are given in Table 3.2. The two possible comparisons a : c and a : d are
considered separately. The following equalities are easily veried.
Lemma 3.7. If a > b and c > d are pairs in v then
12 D. DOR AND J. H ASTAD AND S. ULFBERG AND U. ZWICK
The following inequalities are analogous to the inequalities of Lemma 3.4.
Lemma 3.8. If a > b and c > d are pairs in v and if the number of non-singletons
in v is at most m, for some  < 1, then2
Consider rst the comparison a : c. By examining Table 3.2 and using the equalities
of Lemma 3.7, we get that
w(va<c)+w(va>c )= w abcd= (v)
Minimizing this expression, subject to the equalities of Lemma 3.7, the inequalities of
Lemma 3.8, and the fact that the weights of the nine cases sum up to w(v), amounts
to solving a linear program. By solving this linear program we get that
where
It seems intuitively clear that the comparison a : d is a bad comparison from the
algorithm's point of view. The adversary will most likely answer with a > d. Indeed,
by solving the corresponding linear program, we get that
w(va>d
As for every 0    1, we may disregard the comparison a : d from
any further consideration.
It is easy to verify that (1+f 1 As a result, we get a lower bound
of
This completes the proof of Theorem 3.6.
ON LOWER BOUNDS FOR SELECTING THE MEDIAN 13
4. Concluding remarks. We presented a reformulation of the 2n + o(n) lower
bound of Bent and John for the number of comparisons needed for selecting the
median of n elements. Using this new formulation we obtained an improved lower
bound for pair-forming median nding algorithms. As mentioned, Dor and Zwick [6]
have recently extended the ideas described here and obtained a (2+)n lower bound
for general median nding algorithms, for some tiny  > 0.
We believe that the lower bound for pair-forming algorithms obtained here can
be substantially improved. Such an improvement seems to require, however, some
new ideas. Obtaining an improved lower bound for pair-forming algorithms may be
an important step towards obtaining a lower bound for general algorithms which is
signicantly better than the lower bound of Bent and John [2].
Paterson [11] conjectures that the number of comparisons required for selecting
the median is about (log 4=3 2)n  2:41n.



--R

Producing posets.
Finding the median requires 2n comparisons.
Time bounds for selection.
Partial Order Productions.
Selecting the median.
Median selection requires (2
A tournament problem.
A counting approach to lower bounds for selection problems.
The Art of Computer Programming
A lower bound for determining the median.
Progress in selection.
On lower bounds for computing the i-th largest element

New lower bounds for medians and related problems.
--TR

--CTR
Krzysztof C. Kiwiel, On Floyd and Rivest's SELECT algorithm, Theoretical Computer Science, v.347 n.1-2, p.214-238, November 2005
median selection;lower bounds;comparison algorithms