6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – holf
    Mar 27, 2023 at 17:26

1 Answer 1

13
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.