# 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.

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.
• @JeffE I am confused about the definition of crucial comparison for $y$: the comparisons $y : z$ where either $y < z \le x^{\ast}$ or $x^{\ast} \le z < y$ and $x^{\ast}$ is the target element. What if we don't know the relation between $z$ and $x^{\ast}$ when these comparisons are made? Do we have an oracle here? Or are we omniscient with full information (even the future information in the leaf)? – hengxin Oct 25 '13 at 3:06