10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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)? $\endgroup$ – hengxin Oct 25 '13 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.