Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements without performing any additional comparisons.

I would like to show my solution. I ask you for checking it :)

Let $k$ will be $i$-th element. Let's suppose that we don't know if element $x$ is larger or smaller than $k$
Then it is impossible to know if $k$ is the $i$-th element. Contradiction.

It is very short proof. I can't see reason that it is not correct.

  • 3
    $\begingroup$ That's not a proof, that's a handwaving argument. Besides, "check-my-answers" are unsuited for this platform. So, I recommend you come up with a real proof attempt and a specific question about it. (Also, you should fix what "find" means. Output them all? "Know" which they are? In which sense?) $\endgroup$ – Raphael Aug 14 '15 at 18:27
  • $\begingroup$ The problem is, that I would like to know why this proof is not ok ? $\endgroup$ – M.Swe Aug 14 '15 at 18:30
  • $\begingroup$ So what about this proof: clrs.skanev.com/09/03/04.html Is it ok ? In real there is the same idea. $\endgroup$ – M.Swe Aug 14 '15 at 18:33
  • 4
    $\begingroup$ It's not a proof either, as the author states clearly. There's a difference between an intuitive argument and a proof, which is a series of logical arguments starting from indisputable assumptions and ending with the claim. The main problem is that both of you assume to know how every algorithm for the problem "must" work. That's a common fallacy. The usual way around that is a proof by contradiction: assume an algorithm could solve the problem with fewer comparisons. Construct an input on which it answers incorrectly. $\endgroup$ – Raphael Aug 15 '15 at 6:17

Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is:

Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has exactly $\ell$ elements smaller than it (i.e., it is the $(\ell+1)$st element).

Why is this enough? (The following is somewhat informal. See below for a more formal proof.) Suppose that your comparison algorithm outputs an element $x$ but knows only $j < i-1$ elements smaller than it, that is, in the corresponding partial order, only $j$ elements are smaller than $x$. Then there is some total order in which element $x$ is in position $j+1 < i$, and in particular, you cannot be sure that $x$ is the $i$th element. Similarly, if the algorithm knows only $j < n-i$ elements larger than $x$, then there is some total order in which $x$ is in position $n-j > i$ (using the dual version of the observation). Therefore the only way in which a comparison algorithm can be sure that $x$ is the $i$th element is if in the corresponding partial order, $x$ has exactly $i-1$ elements smaller than it and $n-i$ elements larger than it.

It remains to prove the observation. Given a partial order, we can generate a total order extending it by repeatedly performing the following operation:

Choose a source (a minimal element) $y$, output it, and remove it from the partial order.

This (non-deterministic) algorithm outputs the elements in a certain order which is a total order extending the given partial order.

In order to apply this algorithm to prove the observation, consider the set of elements $P = \{ y : y \leq x \}$ which are at most $x$. In the first $\ell+1$ steps, we always choose a source from $P$ (this is always possible, though this requires an inductive argument). Then it continues in some arbitrary fashion. The resulting total order has $x$ as the $(\ell+1)$st element.

Our argument above, showing how the key observation implies the result, was somewhat informal. Here is a more formal treatment. We will actually show a slightly weaker result, that if a comparison algorithm finds the $i$th element correctly on all inputs with distinct elements, then it "knows" which elements are smaller than the $i$th element (can output them without further comparisons). The stronger result is left as an exercise to the reader.

We can think of the algorithm, when restricted to inputs with distinct elements, as a binary tree: each non-leaf compares two elements and has two children corresponding to the result of the comparison, and each leaf contains the output of the algorithm. We can furthermore assume that each vertex is reachable (we can always prune the tree to ensure this).

We can annotate each vertex with the partial order on the input elements, representing the algorithm's knowledge given the results of the preceding comparisons. We will show that at each leaf with output $x$, the corresponding partial order has exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

The proof is by contradiction. Suppose that there is some leaf with output $x$ at which there are $j < i$ elements smaller than $x$ (the other case, of having less than $n-i$ elements larger than $x$, is handled symmetrically). The key observation shows that there is some linear order $L$ extending the partial order in which $x$ is not the $i$th element. If we had input this linear order to the algorithm, it would have reached the same leaf, and so would have answered incorrectly – contradicting our assumption that the algorithm is valid.

We conclude that at each leaf with output $x$ there are exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

| cite | improve this answer | |
  • 2
    $\begingroup$ Part of your proof assumes that the elements are all distinct (though the core argument still works if they aren't). If a[i] isn't unique, there aren't exactly i-1 smaller elements. $\endgroup$ – Gilles 'SO- stop being evil' Aug 18 '15 at 7:07
  • $\begingroup$ @Gilles That said, the argument is still correct since the algorithm should work, in particular, for inputs with distinct elements. This might not be apparent from the answer since there is a missing paragraph at the end implementing the proof by contradiction mentioned in Raphael's comment to the question. $\endgroup$ – Yuval Filmus Aug 18 '15 at 11:02
  • $\begingroup$ @Gilles The statement of the question assumes that the i-th smallest element is unique, and that all others are either smaller or larger. $\endgroup$ – babou Aug 18 '15 at 16:37

Let me give some insight, as I do not claim it proves it ;) If algorithm uses comparisons to find $i$th element it means there is order of elements, as it must tell apart smaller and greater elements. It is not totally ordered as it partition set by pivot (which is $i$th element), but cannot tell ordere inside these two parts.

Here comes transitivity of comparison ($a < b \wedge b < c$ implies $a < c$). So after performing original number of comparisons we can deduce (not compare) which elements are in which part, due to transitivity. If we build graph (as proposed on the site) while taking comparisons we add one edge per comparison.

Now we can traverse graph to tell these two sets apart (smaller than pivot and second greater then pivot).

Now if we suppose that there exists some number $v$ in this set that we do not know whether is smaller or greater. This contradicts finding $i$th element in first place, so it would imply that $v$ was not compared to any number in set, therefore it would be not possible to determine $i$th element.

I do not claim this is proof, and I have rewritten in better structured way what I have tried to point out earlier.

| cite | improve this answer | |
  • $\begingroup$ Can you refer to my proposition of proof ? $\endgroup$ – M.Swe Aug 14 '15 at 18:51
  • $\begingroup$ While I can follow the reasoning (it's the same proof as Yuval's, explained differently), it's difficult to see from the way you explained how that last part by contradiction works. $\endgroup$ – Gilles 'SO- stop being evil' Aug 18 '15 at 7:10
  • 1
    $\begingroup$ I assume that it comes from definition of $i$th element (weak ordering), so by contradiction of necessary condition of existence of $n$th element, it ends claim. Is it too fast assumption? $\endgroup$ – Evil Aug 18 '15 at 14:28
  • $\begingroup$ You correctly understand my idea $\endgroup$ – M.Swe Aug 18 '15 at 14:38

You just declare an equivalent statement of the problem in a different way without a proof. How can you prove that in order to know k is i-th order statistics, for every other element x, the position of x regard to k must be known?

The proof from here http://clrs.skanev.com/09/03/04.html is also wrong. To know relative position of x and k, we do not necessarily perform comparison between x and k, e.g., if x < y, and y < k then we know that x < k without doing any comparison between x and k, so there is not edge pointing from node x to k because there is no comparison between them.

This problem is not that easy!

| cite | improve this answer | |

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.