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$ The FAQ discourages answers that are barely more than a link to an external site (even if the link is excellent). $\endgroup$ – Joe Apr 20 '12 at 7:47
  • $\begingroup$ @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 ? $\endgroup$ – Massimo Cafaro Apr 20 '12 at 9:32
  • 1
    $\begingroup$ @unforgiven: See under "Why are some questions or answers removed?" — "Barely more than a link to an external site". $\endgroup$ – JeffE Apr 20 '12 at 10:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Gilles Apr 20 '12 at 13:07
  • 1
    $\begingroup$ X\L is the set difference operation. $\endgroup$ – Massimo Cafaro Apr 23 '12 at 9:45

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.