Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
