# Find odd-ranked numbers from a list

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?

• 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
Mar 27, 2023 at 17:26

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

• Nice! Though I don't understand why the word "sketch" was used ;) . Mar 28, 2023 at 3:53
• 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)$. Mar 29, 2023 at 2:28
• 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. Apr 1, 2023 at 20:44
• @ReinstateMonica, no, wait, ${n\choose n/2} = \Theta(2^n/\sqrt n)$, so $\log_2{n\choose n/2} = \Theta(n)$. Apr 1, 2023 at 21:15
• @NealYoung Ah, you are right, good catch! Apr 3, 2023 at 17:47