<p><strong>Lemma 1.</strong> <em>Any comparison-based algorithm requires <span class="math-container">$\Omega(n\log n)$</span> comparisons in the worst case.</em></p>
<p><em>Proof sketch.</em> Let <span class="math-container">$A$</span> be any comparison-based algorithm for the problem.  Let <span class="math-container">$x=(x_1, x_2, \ldots, x_n)$</span> be an arbitrary permutation of <span class="math-container">$[n]$</span>, considered as an instance of the problem.  I will argue that in order to solve <span class="math-container">$x$</span> (that is, to identify the odd-ranked elements of <span class="math-container">$x$</span>, given <span class="math-container">$x$</span>), <span class="math-container">$A$</span> has to sort <span class="math-container">$x$</span>.  The lemma will follow by the well-known result that any comparison-based sorting algorithm requires <span class="math-container">$\Omega(n\log n)$</span> comparisons.</p>
<p>Consider the execution of <span class="math-container">$A$</span> on <span class="math-container">$x$</span>.  Suppose for contradiction that at termination the comparisons that <span class="math-container">$A$</span> has done do not suffice to sort <span class="math-container">$x$</span>. Then, for some <span class="math-container">$x_i$</span> and <span class="math-container">$x_j = x_i+1$</span>, <span class="math-container">$A$</span> never directly compared <span class="math-container">$x_i$</span> and <span class="math-container">$x_j$</span>.</p>
<p>Consider executing <span class="math-container">$A$</span> on the input <span class="math-container">$x'$</span> obtained from <span class="math-container">$A$</span> by swapping the values of <span class="math-container">$x_i$</span> and <span class="math-container">$x_j$</span>.  Inductively, the sequence of comparisons that <span class="math-container">$A$</span> makes will be exactly the same as it made on input <span class="math-container">$x$</span>, because for every comparison <span class="math-container">$x'_a &lt; x'_b ?$</span>, the outcome is the same as the corresponding comparison <span class="math-container">$x_a &lt; x_b ?$</span> for <span class="math-container">$x$</span>, unless <span class="math-container">$\{a, b\} = \{i, j\}$</span>, but the comparison <span class="math-container">$x'_i &lt; x'_j ?$</span> is never made.</p>
<p>So <span class="math-container">$A$</span> outputs the same subset of the given variables for <span class="math-container">$x$</span> as it does for <span class="math-container">$x'$</span>.  One of these two outputs must be wrong, contradicting the correctness of <span class="math-container">$A$</span> <span class="math-container">$~~~\Box$</span>.</p>

CC BY-SA 4.0
2023-03-28T03:53:34.867Z
Nice! Though I don't understand why the word "sketch" was used ;) .
mathworker21
CC BY-SA 4.0
2023-03-29T02:28:22.987Z
This answer can be stated more concisely: across all permutations of $[n]$, there are $n C \frac{n}{2}$ index sets that the oddly ranked items take. Therefore any BDD, such as one induced by pairwise computations, must have depth at least $\log_2(n C \frac{n}{2}) \in \theta(n \log n)$.
Reinstate Monica
CC BY-SA 4.0
2023-04-01T20:44:43.533Z
I suspect that the $Ω(n \log n)$ comparisons result holds even if we have to classify just an expected $1/2+ε$ (for $Ω(1)$ $ε$) fraction of the elements correctly as to whether their rank is odd or even.
Dmytro Taranovsky
CC BY-SA 4.0
2023-04-01T21:15:54.110Z
@ReinstateMonica, no, wait, ${n\choose n/2} = \Theta(2^n/\sqrt n)$, so $\log_2{n\choose n/2} = \Theta(n)$.
Neal Young
CC BY-SA 4.0
2023-04-03T17:47:39.197Z
@NealYoung Ah, you are right, good catch!
Reinstate Monica
CC BY-SA 4.0
2023-04-04T01:16:06.883Z
@DmytroTaranovsky, by "classify the rank of $k$ elements correctly", do you mean that the algorithm reports, for some $k$ elements of its choice, what the parities of the ranks are?  Or do you mean that it classifies all elements and gets at least $k$ right (but we don't know which)?
Neal Young
CC BY-SA 4.0
2023-04-05T05:35:36.623Z
@NealYoung I meant the latter (hence the use of $1/2+ε$ rather than $ε$). With $o(n \log n)$ comparisons, for typical elements there should be enough uncertainty about rank that the parity is almost random (though I am not sure how to prove it).
Dmytro Taranovsky
CC BY-SA 4.0
2023-03-27T18:01:57.083Z
2023-03-27T19:13:11.267Z
2023-03-27T19:13:11.267Z
Neal Young
<p>From a list of <span class="math-container">$n$</span> distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?</p>
<p>I could sort the whole list using <span class="math-container">$O(n\log n)$</span> queries, but that gives me more information than I need. On the other hand, the classic argument that sorting requires <span class="math-container">$\Omega(n\log n)$</span> queries only yields that my task requires roughly <span class="math-container">$\Omega(n)$</span> queries. Is it possible to do my task in <span class="math-container">$O(n)$</span> queries?</p>

CC BY-SA 4.0
2023-03-27T17:26:17.890Z
If you need them sorted then it reduces to sorting the array: find the odd-ranked numbers with $g(n)$ queries, remove the minimum from the array and find the odd-ranked numbers from this new array with $g(n-1)$ queries and merge both lists with $O(n)$ queries, hence a total of $O(g(n)+n)$ queries.
holf
<ds.algorithms><lower-bounds><sorting>
Find odd-ranked numbers from a list
TZM
# Find odd-ranked numbers from a list

(Asked by: username_0 on 2023-03-27)

From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?

I could sort the whole list using $O(n\log n)$ queries, but that gives me more information than I need. On the other hand, the classic argument that sorting requires $\Omega(n\log n)$ queries only yields that my task requires roughly $\Omega(n)$ queries. Is it possible to do my task in $O(n)$ queries?

**Tags:** ds.algorithms, lower-bounds, sorting

> **Comments:**
> **username_1**: If you need them sorted then it reduces to sorting the array: find the odd-ranked numbers with $g(n)$ queries, remove the minimum from the array and find the odd-ranked numbers from this new array with $g(n-1)$ queries and merge both lists with $O(n)$ queries, hence a total of $O(g(n)+n)$ queries.  

---

## 1 answers

### Answer by username_2 on 2023-03-27. Score: 13 | Accepted answer

**Lemma 1.** *Any comparison-based algorithm requires $\Omega(n\log n)$ comparisons in the worst case.*

*Proof sketch.* Let $A$ be any comparison-based algorithm for the problem. Let $x=(x\_1, x\_2, \ldots, x\_n)$ be an arbitrary permutation of $[n]$, considered as an instance of the problem. I will argue that in order to solve $x$ (that is, to identify the odd-ranked elements of $x$, given $x$), $A$ has to sort $x$. The lemma will follow by the well-known result that any comparison-based sorting algorithm requires $\Omega(n\log n)$ comparisons.

Consider the execution of $A$ on $x$. Suppose for contradiction that at termination the comparisons that $A$ has done do not suffice to sort $x$. Then, for some $x\_i$ and $x\_j = x\_i+1$, $A$ never directly compared $x\_i$ and $x\_j$.

Consider executing $A$ on the input $x'$ obtained from $A$ by swapping the values of $x\_i$ and $x\_j$. Inductively, the sequence of comparisons that $A$ makes will be exactly the same as it made on input $x$, because for every comparison $x'\_a < x'\_b ?$, the outcome is the same as the corresponding comparison $x\_a < x\_b ?$ for $x$, unless $\{a, b\} = \{i, j\}$, but the comparison $x'\_i < x'\_j ?$ is never made.

So $A$ outputs the same subset of the given variables for $x$ as it does for $x'$. One of these two outputs must be wrong, contradicting the correctness of $A$ $~~~\Box$.

> **Comments:**
> **username_3**: Nice! Though I don't understand why the word "sketch" was used ;) .  
> **username_4**: This answer can be stated more concisely: across all permutations of $[n]$, there are $n C \frac{n}{2}$ index sets that the oddly ranked items take. Therefore any BDD, such as one induced by pairwise computations, must have depth at least $\log_2(n C \frac{n}{2}) \in \theta(n \log n)$.  
> **username_5**: I suspect that the $Ω(n \log n)$ comparisons result holds even if we have to classify just an expected $1/2+ε$ (for $Ω(1)$ $ε$) fraction of the elements correctly as to whether their rank is odd or even.  
> **username_2**: @ReinstateMonica, no, wait, ${n\choose n/2} = \Theta(2^n/\sqrt n)$, so $\log_2{n\choose n/2} = \Theta(n)$.  
> **username_4**: @NealYoung Ah, you are right, good catch!  
> **username_2**: @DmytroTaranovsky, by "classify the rank of $k$ elements correctly", do you mean that the algorithm reports, for some $k$ elements of its choice, what the parities of the ranks are?  Or do you mean that it classifies all elements and gets at least $k$ right (but we don't know which)?  
> **username_5**: @NealYoung I meant the latter (hence the use of $1/2+ε$ rather than $ε$). With $o(n \log n)$ comparisons, for typical elements there should be enough uncertainty about rank that the parity is almost random (though I am not sure how to prove it).  

---

