# Lower bound for finding kth smallest element using adversary arguments

In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument?

Wikipedia says that tournament algorithm runs in $O(n+k\log n)$, and $n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$ is given as lower bound.

I am going to briefly outline a sketch of an adversary argument.

Consider your selection algorithm playing against an opponent that we will call the adversary.The aim of the adversary is to provide an input $X$ for your algorithm that maximizes the number of comparison operations done by your algorithm. Indeed, your algorithm can be seen as a comparison tree, in which a path corresponds to a partial order. When the algorithm asks the adversary about a pair $(x, y)$ of elements, the adversary returns either $x < y$ or $y < x$. The adversary answers can never contradict previous outcomes.

Assume that the $k$-th largest element is $x^*$: considering the partial order associated to any leaf of the comparison tree, then $x^*$ must be comparable with every other element in order for the algorithm to be correct, so that the algorithm must have made at least one comparison $(y, z)$ $\forall y \neq x^*$ whose outcome is either $y < z \leq x^*$ or $x^* \leq z < y$. Call such a comparison crucial for an element $y$. Obviously, the adversary wants to maximize the number of non crucial comparisons done by your algorithm.

Let $L$ be the set of $k−1$ largest elements; your algorithm needs to correctly identify all of the elements in $L$ and also the largest element in $X \setminus L$, i.e. $x^*$. Observe that each element in $X \setminus L$ has lost at least one crucial comparison. Now, the adversary has a strategy that forces each of the $k - 1$ elements in $L$ to win at least $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$ comparisons, none of which is crucial for $X \setminus L$. Adding the remaining $n - k$ crucial comparisons for $X \setminus L$ you obtain the lower bound. For details, please read the following, excellent, Jeff Erikson notes.

• The FAQ discourages answers that are barely more than a link to an external site (even if the link is excellent). – Joe Apr 20 '12 at 7:47
• @Joe: where exactly in the FAQ did you read this? I did not find this in the FAQ. Anyway, does it really make sense to cut and paste materials publicly available on a web site? Why write a lengthly answer, just to add at the ends credits and provenance ? – Massimo Cafaro Apr 20 '12 at 9:32
• @unforgiven: See under "Why are some questions or answers removed?" — "Barely more than a link to an external site". – JeffE Apr 20 '12 at 10:03
• @unforgiven Please read how to answer, which is linked (admittedly discretely) from the faq. A quick (a couple of sentences) summary of Jeff Erikson's notes would be nice. – Gilles 'SO- stop being evil' Apr 20 '12 at 13:07
• X\L is the set difference operation. – Massimo Cafaro Apr 23 '12 at 9:45