<p>I believe here is a different proof, proving the impossibility of an $\mathcal{O}(\log ^k n)$ query time structure, with $\mathcal{O}(n)$ pre-processing.</p>

<p>Suppose in the preprocessing you do $\mathcal{O}(n)$ comparisons, leading to a partial order.</p>

<p>Now consider the size $A$ of the largest antichain in that. Since these elements are not comparable, for us to have an $\mathcal{O}(\log ^k n)$ query algorithm, we must have that $A = \mathcal{O}(\log ^k n)$.</p>

<p>Now by Dilworth's theorem, there is a partition of size $A$, into chains.</p>

<p>Now we can complement the algorithm to determine the chains in the partition. We can determine if two elements are comparable by creating a directed graph of comparisons and doing a reachability analysis. This can be done without any additional comparisons. Now just brute force out each possible partition of size $A$ to determine if it is a partition of chains. </p>

<p>Once we have the chains, we can merge them to give an $\mathcal{O}(n \log \log n)$ comparisons algorithm for sorting the whole list.</p>

CC BY-SA 3.0
2011-09-19T21:26:10.917Z
@Yuval: thinking about the proofs, I only see that you must have either $\Omega(n \log n)$ preprocessing or $\Omega(n^{1-\epsilon})$ query time for all $\epsilon$. It's possible to have $o(n \log n)$ preprocessing time and $O(n / \log n)$ query time. One can divide the list into $\log n$ lists of size $n/\log n$ each in time $\theta(n \log\log n)$ using repeated median-finding.
Peter Shor 
CC BY-SA 3.0
2011-08-23T20:49:06.833Z
This is a nice idea. And if you could show that the chain partition must be known to the algorithm then you could use mergesort to show that it would only take an additional O(n log log n) comparisons to sort the whole input, rather than using Jensen. But there is a problem: why must the preprocessing algorithm construct a chain partition? A chain partition must exist, yes, but that's very different from it being known to the algorithm.
David Eppstein
CC BY-SA 3.0
2011-08-23T20:55:44.210Z
@David: We should be able to complement the algorithm to construct the partitions without doing any additional comparisons, for instance by considering every possible partition and checking if it is a chain partition. All we need to know is whether two elements are comparable, which I suppose we can do by some reachability analysis on the directed graph of compares. We don't need to do any additional compares. And given a 'bag' of elements which form a chain, we should be able to arrange them in ascending order (i.e. sort them) without doing any more compares.
Aryabhata
CC BY-SA 3.0
2011-08-23T21:46:49.437Z
The last paragraph seems to be lacking. It could happen that on a specific input, $n-1$ comparisons are enough to determine the entire total order. What you need to show is that *sometimes* you'll get an underdetermined partial order.
Yuval Filmus
CC BY-SA 3.0
2011-08-23T22:08:06.770Z
@Yuval: "In the worst case" is implicit (but could have potential holes). David's suggestion makes it more clear. I will edit. Thanks.
Aryabhata
CC BY-SA 3.0
2011-08-23T23:08:43.627Z
Ok, I now believe this proof. And it shows more strongly that to achieve polylog query time you have to use a number of comparisons that's within an additive $O(n\log\log n)$ of sorting. Nice. By the way, the chain partition can be found in polynomial time from the set of comparisons already performed, rather than needing a brute force search, but that doesn't make any difference for your argument.
David Eppstein
CC BY-SA 3.0
2011-08-26T15:12:24.957Z
The proofs actually show that you must have either $\Omega(n\log n)$ preprocessing or $\Omega(n)$ for each query. Of course both are tight. This shows that binary search and linear search are the only "interesting" search algorithms (at least in the classical world).
Yuval Filmus
CC BY-SA 3.0
2011-08-31T01:05:24.550Z
@Yuval: maybe you should write up this observation as an actual answer, because it seems to me that you have to do a moderate amount of work to get the above result from the proofs in the answers.
Peter Shor 
CC BY-SA 3.0
2011-08-23T19:31:13.800Z
2017-08-09T18:05:37.377Z
2017-08-09T18:05:37.377Z
Aryabhata
<p>As Peter Shor's answer notes, to rule out membership in a comparison-based model, we need to know how the element compares with every member.  Thus, using $k&lt;n$ random queries (the number of members smaller than the queried nonmember is random), we gain $Θ(n \log k)$ information relative to having $n$ unsorted values.  Therefore, for some constant $c&gt;0$, using $c \, n \log k$ preprocesssing, we cannot have $≤c \, n \log k/k$ query cost.  This is optimal up to a constant factor since we can sort the data into $k' = k / \log k ≤ n/\log n$ approximately equal buckets (each bucket unsorted) in $O(n \log k') = O(n \log k)$ time, which allows $O(n/k')$ query cost.</p>

<p>In particular, using $O(n)$ preprocessing, we cannot have $o(n)$ query cost. Also, $o(n \log n)$ preprocessing corresponds to $k$ in $O(n^ε)$ for every $ε&gt;0$ and thus $Ω(n^{1−ε})$ query cost.</p>

CC BY-SA 3.0
2017-09-19T22:46:58.053Z
2017-09-19T23:20:29.463Z
2017-09-19T23:20:29.463Z
Dmytro Taranovsky
<p>Here's a proof that it's impossible. Suppose you could build such a data structure. Build it. Then choose $n/\log n$ items at random from the list, add $\epsilon$ to each of them, where $\epsilon$ is smaller than the difference between any two items on the list, and perform the queries to check whether any of the resulting items is in the list. You've performed $O(n)$ queries so far. </p>

<p>I would like to claim that the comparisons you have done are sufficient to tell whether an item $a$ on the original list is smaller than or larger than any new item $b$. Suppose you couldn't tell. Then, because this is a comparison-based model, you wouldn't know whether $a$ was equal to $b$ or not, a contradiction of the assumption that your data structure works.</p>

<p>Now, since the $n/\log n$ items you chose were random, your comparisons have with high probability given enough information to divide the original list into $n/\log n$ lists each of size $O(\log n)$. By sorting each of these lists, you get a randomized $O(n \log \log n)$-time sorting algorithm based solely on comparisons, a contradiction.</p>

CC BY-SA 3.0
2011-08-21T13:17:26.733Z
A few hints to help understanding the proof (assuming I understand it correctly myself of course): the $b$ items should be filled in by the items after $\epsilon$ has been added to them; the comparison model guarantees you know which of the cases $a \leq b$ and $a \geq b$ holds; the $n / \log n$ lists are in 'ascending order': every element in any higher list is higher than every element in any lower list; after the original queries you have enough *information* to make the lists around the items you randomly chose,
Alex ten Brink
CC BY-SA 3.0
2011-08-21T13:17:38.497Z
(continued) note that you don't even have to explicitly be able to build the list in the provided time for the proof to hold.
Alex ten Brink
CC BY-SA 3.0
2011-08-21T17:40:14.050Z
I don't quiet understand this proof. The final contradiction is off "algorithm based solely on comparisons", but in the first steps of our algorithm we added $\epsilon$ to each item (further, "where $\epsilon$ is smaller than the difference between any two items on the list"). Why are we still justified that our algorithm still only comparison based if we assumed our items have a non-discrete total order on them?
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-21T18:48:16.290Z
@Artem: Your original input consists of elements $x \in X$. Then you construct a new set $X' = X \times \{0,1\}$; you represent an original $x \in X$ as $(x,0) \in X'$ and a modified $x + \epsilon$ as $(x,1) \in X'$. Now you use the black box algorithm; the algorithm compares elements of $X'$ to each other; to answer such queries, you only need to compare a constant number of elements of $X$ to each other. Hence everything should be doable in the comparison model, with a constant overhead.
Jukka Suomela
CC BY-SA 3.0
2011-08-22T13:24:48.723Z
@Alex "note that you don't even have to explicitly be able to build the list in the provided time for the proof to hold." why? I don't see how to sort those lists without construct them...
Chao Xu
CC BY-SA 3.0
2011-08-22T13:48:16.113Z
nvm I understand, construct the list doesn't need any more comparisons, and for sorting only comparisons should be counted.
Chao Xu
CC BY-SA 3.0
2011-08-23T19:04:43.510Z
I am pretty sure I am missing something. Doesn't this also disprove existence of an $O(\log^2n)$ algorithm (which exists)? (Replacing $n/\log n$ by $n/\log^2 n$ throughout). Thanks.
Aryabhata
CC BY-SA 3.0
2011-08-23T19:08:07.007Z
@Aryabhata: it does. What is the $O(\log^2 n)$ algorithm?
Peter Shor 
CC BY-SA 3.0
2011-08-23T19:12:03.817Z
@Peter: Hmm... I thought there was one, but I believe that is where I must be mistaken. Thank you.
Aryabhata
CC BY-SA 3.0
2011-08-21T11:50:23.773Z
2011-08-21T11:50:23.773Z
Peter Shor 
<p>Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?</p>

<p>I really think there isn't, so a proof that there is none is also welcomed.</p>

CC BY-SA 3.0
2011-08-18T09:42:18.403Z
So you do consider expected time?
Raphael
CC BY-SA 3.0
2011-08-18T10:38:05.490Z
@Raphael, I don't understand. Of course I consider the expected time, that's actually the only limitation I pose.
Chi-Lan
CC BY-SA 3.0
2011-08-18T11:10:27.510Z
So, on the first case, is the list sorted when you search it?
Filip Ekberg
CC BY-SA 3.0
2011-08-18T12:10:44.903Z
@Filip, no the list is never sorted. Sorted list is a data structure you can use in order to find an element in the list quickly.
Chi-Lan
CC BY-SA 3.0
2011-08-18T12:32:26.143Z
(1) I do not know why you can say “Of course I consider the expected time,” because you do not state “expected” in your question at all.  Please try to state your question more precisely before saying “of course.”  (2) Please define “non-hashable.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T12:46:09.180Z
@Tsuyoshi @Raphael I apologize, I didn't understand that in English expected time means `E[time]`. I thought Raphael meant "do you care about the running time. So no, I speak about worst case time. (2) non-hashable, you are not allowed to calculate the hash of those items. You cannot use a hash table for this values. The only allowed action is to compare two values in the list.
Chi-Lan
CC BY-SA 3.0
2011-08-18T12:54:26.170Z
(1) I see.  Thanks for the explanation.  If someone asked “Do you care about the running time?” then the answer would be indeed “of course.” :)  (2) I think that “The only allowed action is to compare two values in the list” is much more precise than just stating “non-hashable.”  Can you edit the question so that people do not have to read the comments to understand what “non-hashable” means?
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T12:56:21.083Z
By the way, if you cannot prove it, why do you know it is impossible?  If it is an exercise in a textbook or a class, you are asking on a wrong website.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T12:59:18.457Z
I'm not entirely sure, but it looks very "reasonable". I know it's impossible, generally speaking, to sort a list with comparison-only model with less than `O(n log n)`, and I know that all known data structures which are based on comparison only (heap, red-black tree, etc), cannot be built with less than `O(n log n)`, so I'll be very surprised to know that it's possible. (I don't think that it's a known open problem, because I never heard of it, but maybe it is, I don't know).
Chi-Lan
CC BY-SA 3.0
2011-08-18T13:01:36.443Z
And just to refer to your "accusations". It is not a problem in a text book. It thought about it when trying to solve a puzzle I heard.
Chi-Lan
CC BY-SA 3.0
2011-08-18T13:03:52.163Z
"all known data structures which are based on comparison only (heap ". Heap can be built in $O(n)$ time.
Chao Xu
CC BY-SA 3.0
2011-08-18T13:07:40.923Z
@Chi-Lan, you can't perform a `O(log n)` search on an unsorted/not balanced data structure.
Filip Ekberg
CC BY-SA 3.0
2011-08-18T13:11:02.167Z
Is this your question: Is there a data structure that takes an unordered array of n items, performs preprocessing in O(n) and answers queries: is there some element x on the list, each query in worst time O(log n)?
sdcvvc
CC BY-SA 3.0
2011-08-18T13:18:45.040Z
Just in case anyone is trying to prove the opposite. Here is one idea: generate $O(n/\log n)$ list of size $O(\log n)$, locate which list contains the element in $O(\log n)$ time and do a linear search. One have to come up with a clever way to generate the lists. The naive candidate "partition the list such that all element in one list is smaller than the next one" can't be done in $O(n)$ time.(since one can use it recursively and show sorting is $O(n)$).
Chao Xu
CC BY-SA 3.0
2011-08-18T13:25:03.750Z
@sdcvvc exactly, I'm editing your question it in. One cavaet, the algorithm must only compare between two elements of the list.
Chi-Lan
CC BY-SA 3.0
2011-08-18T13:29:01.450Z
@Filip: Is that easy to see?  If it is true, then I agree that it solves the question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T21:41:17.940Z
@Tsuyoshi Ito, Hmm, I don't know the correct way to express a "Proof" but by example, maybe? Let me think about it a bit more..
Filip Ekberg
CC BY-SA 3.0
2011-08-19T15:18:49.390Z
@Filip: You want an adversary argument. Take the $O(n)$ preprocessing algorithm. It lumps together $n!/\exp(n)$ of the permutations to the same state. Now take the query algorithm, and find a sequence of consistent answers for some query $x$ for which the algorithm answers "no" without knowing for sure. The partial queries reduce the space of permutations (e.g. if $x<a$ and $b<x$ then $b<a$). You only know that $x$ is not there if $a<x<b$ for two adjacent $a,b$ (adjacent on all permutations!) or $x<a_{\min}$ or $x>a_{\max}$.
Yuval Filmus
CC BY-SA 3.0
2011-08-20T15:59:33.870Z
Alternatively, run the same adversary argument, and show that it impossible that for all $n$ possible "yes" queries, the algorithm will answer "yes" honestly (i.e. find the actual element).
Yuval Filmus
CC BY-SA 3.0
2011-08-20T16:13:39.937Z
Is there any reason that no one is actually answering :), and just using the comments ?
Suresh Venkat
<ds.data-structures><sorting>
Comparison-based data structure for finding items
Chi-Lan
# Comparison-based data structure for finding items

(Asked by: username_0 on 2011-08-18)

Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?

I really think there isn't, so a proof that there is none is also welcomed.

**Tags:** ds.data-structures, sorting
> **Comments:**
> **username_1**: So you do consider expected time?  
> **username_0**: @Raphael, I don't understand. Of course I consider the expected time, that's actually the only limitation I pose.  
> **username_2**: So, on the first case, is the list sorted when you search it?  
> **username_0**: @Filip, no the list is never sorted. Sorted list is a data structure you can use in order to find an element in the list quickly.  
> **username_3**: (1) I do not know why you can say “Of course I consider the expected time,” because you do not state “expected” in your question at all.  Please try to state your question more precisely before saying “of course.”  (2) Please define “non-hashable.”  
> **username_0**: @Tsuyoshi @Raphael I apologize, I didn't understand that in English expected time means `E[time]`. I thought Raphael meant "do you care about the running time. So no, I speak about worst case time. (2) non-hashable, you are not allowed to calculate the hash of those items. You cannot use a hash table for this values. The only allowed action is to compare two values in the list.  
> **username_3**: (1) I see.  Thanks for the explanation.  If someone asked “Do you care about the running time?” then the answer would be indeed “of course.” :)  (2) I think that “The only allowed action is to compare two values in the list” is much more precise than just stating “non-hashable.”  Can you edit the question so that people do not have to read the comments to understand what “non-hashable” means?  
> **username_3**: By the way, if you cannot prove it, why do you know it is impossible?  If it is an exercise in a textbook or a class, you are asking on a wrong website.  
> **username_0**: I'm not entirely sure, but it looks very "reasonable". I know it's impossible, generally speaking, to sort a list with comparison-only model with less than `O(n log n)`, and I know that all known data structures which are based on comparison only (heap, red-black tree, etc), cannot be built with less than `O(n log n)`, so I'll be very surprised to know that it's possible. (I don't think that it's a known open problem, because I never heard of it, but maybe it is, I don't know).  
> **username_0**: And just to refer to your "accusations". It is not a problem in a text book. It thought about it when trying to solve a puzzle I heard.  
> **username_4**: "all known data structures which are based on comparison only (heap ". Heap can be built in $O(n)$ time.  
> **username_2**: @Chi-Lan, you can't perform a `O(log n)` search on an unsorted/not balanced data structure.  
> **username_5**: Is this your question: Is there a data structure that takes an unordered array of n items, performs preprocessing in O(n) and answers queries: is there some element x on the list, each query in worst time O(log n)?  
> **username_4**: Just in case anyone is trying to prove the opposite. Here is one idea: generate $O(n/\log n)$ list of size $O(\log n)$, locate which list contains the element in $O(\log n)$ time and do a linear search. One have to come up with a clever way to generate the lists. The naive candidate "partition the list such that all element in one list is smaller than the next one" can't be done in $O(n)$ time.(since one can use it recursively and show sorting is $O(n)$).  
> **username_0**: @sdcvvc exactly, I'm editing your question it in. One cavaet, the algorithm must only compare between two elements of the list.  
> **username_3**: @Filip: Is that easy to see?  If it is true, then I agree that it solves the question.  
> **username_2**: @Tsuyoshi Ito, Hmm, I don't know the correct way to express a "Proof" but by example, maybe? Let me think about it a bit more..  
> **username_6**: @Filip: You want an adversary argument. Take the $O(n)$ preprocessing algorithm. It lumps together $n!/\exp(n)$ of the permutations to the same state. Now take the query algorithm, and find a sequence of consistent answers for some query $x$ for which the algorithm answers "no" without knowing for sure. The partial queries reduce the space of permutations (e.g. if $x<a$ and $b<x$ then $b<a$). You only know that $x$ is not there if $a<x<b$ for two adjacent $a,b$ (adjacent on all permutations!) or $x<a_{\min}$ or $x>a_{\max}$.  
> **username_6**: Alternatively, run the same adversary argument, and show that it impossible that for all $n$ possible "yes" queries, the algorithm will answer "yes" honestly (i.e. find the actual element).  
> **username_7**: Is there any reason that no one is actually answering :), and just using the comments ?  

---

## 3 answers

### Answer by username_9 on 2011-08-21. Score: 30 | Accepted answer

Here's a proof that it's impossible. Suppose you could build such a data structure. Build it. Then choose $n/\log n$ items at random from the list, add $\epsilon$ to each of them, where $\epsilon$ is smaller than the difference between any two items on the list, and perform the queries to check whether any of the resulting items is in the list. You've performed $O(n)$ queries so far.

I would like to claim that the comparisons you have done are sufficient to tell whether an item $a$ on the original list is smaller than or larger than any new item $b$. Suppose you couldn't tell. Then, because this is a comparison-based model, you wouldn't know whether $a$ was equal to $b$ or not, a contradiction of the assumption that your data structure works.

Now, since the $n/\log n$ items you chose were random, your comparisons have with high probability given enough information to divide the original list into $n/\log n$ lists each of size $O(\log n)$. By sorting each of these lists, you get a randomized $O(n \log \log n)$-time sorting algorithm based solely on comparisons, a contradiction.

> **Comments:**
> **username_12**: A few hints to help understanding the proof (assuming I understand it correctly myself of course): the $b$ items should be filled in by the items after $\epsilon$ has been added to them; the comparison model guarantees you know which of the cases $a \leq b$ and $a \geq b$ holds; the $n / \log n$ lists are in 'ascending order': every element in any higher list is higher than every element in any lower list; after the original queries you have enough *information* to make the lists around the items you randomly chose,  
> **username_12**: (continued) note that you don't even have to explicitly be able to build the list in the provided time for the proof to hold.  
> **username_13**: I don't quiet understand this proof. The final contradiction is off "algorithm based solely on comparisons", but in the first steps of our algorithm we added $\epsilon$ to each item (further, "where $\epsilon$ is smaller than the difference between any two items on the list"). Why are we still justified that our algorithm still only comparison based if we assumed our items have a non-discrete total order on them?  
> **username_14**: @Artem: Your original input consists of elements $x \in X$. Then you construct a new set $X' = X \times \{0,1\}$; you represent an original $x \in X$ as $(x,0) \in X'$ and a modified $x + \epsilon$ as $(x,1) \in X'$. Now you use the black box algorithm; the algorithm compares elements of $X'$ to each other; to answer such queries, you only need to compare a constant number of elements of $X$ to each other. Hence everything should be doable in the comparison model, with a constant overhead.  
> **username_4**: @Alex "note that you don't even have to explicitly be able to build the list in the provided time for the proof to hold." why? I don't see how to sort those lists without construct them...  
> **username_4**: nvm I understand, construct the list doesn't need any more comparisons, and for sorting only comparisons should be counted.  
> **username_8**: I am pretty sure I am missing something. Doesn't this also disprove existence of an $O(\log^2n)$ algorithm (which exists)? (Replacing $n/\log n$ by $n/\log^2 n$ throughout). Thanks.  
> **username_9**: @Aryabhata: it does. What is the $O(\log^2 n)$ algorithm?  
> **username_8**: @Peter: Hmm... I thought there was one, but I believe that is where I must be mistaken. Thank you.  

---

### Answer by username_8 on 2011-08-23. Score: 24

I believe here is a different proof, proving the impossibility of an $\mathcal{O}(\log ^k n)$ query time structure, with $\mathcal{O}(n)$ pre-processing.

Suppose in the preprocessing you do $\mathcal{O}(n)$ comparisons, leading to a partial order.

Now consider the size $A$ of the largest antichain in that. Since these elements are not comparable, for us to have an $\mathcal{O}(\log ^k n)$ query algorithm, we must have that $A = \mathcal{O}(\log ^k n)$.

Now by Dilworth's theorem, there is a partition of size $A$, into chains.

Now we can complement the algorithm to determine the chains in the partition. We can determine if two elements are comparable by creating a directed graph of comparisons and doing a reachability analysis. This can be done without any additional comparisons. Now just brute force out each possible partition of size $A$ to determine if it is a partition of chains.

Once we have the chains, we can merge them to give an $\mathcal{O}(n \log \log n)$ comparisons algorithm for sorting the whole list.

> **Comments:**
> **username_10**: This is a nice idea. And if you could show that the chain partition must be known to the algorithm then you could use mergesort to show that it would only take an additional O(n log log n) comparisons to sort the whole input, rather than using Jensen. But there is a problem: why must the preprocessing algorithm construct a chain partition? A chain partition must exist, yes, but that's very different from it being known to the algorithm.  
> **username_8**: @David: We should be able to complement the algorithm to construct the partitions without doing any additional comparisons, for instance by considering every possible partition and checking if it is a chain partition. All we need to know is whether two elements are comparable, which I suppose we can do by some reachability analysis on the directed graph of compares. We don't need to do any additional compares. And given a 'bag' of elements which form a chain, we should be able to arrange them in ascending order (i.e. sort them) without doing any more compares.  
> **username_6**: The last paragraph seems to be lacking. It could happen that on a specific input, $n-1$ comparisons are enough to determine the entire total order. What you need to show is that *sometimes* you'll get an underdetermined partial order.  
> **username_8**: @Yuval: "In the worst case" is implicit (but could have potential holes). David's suggestion makes it more clear. I will edit. Thanks.  
> **username_10**: Ok, I now believe this proof. And it shows more strongly that to achieve polylog query time you have to use a number of comparisons that's within an additive $O(n\log\log n)$ of sorting. Nice. By the way, the chain partition can be found in polynomial time from the set of comparisons already performed, rather than needing a brute force search, but that doesn't make any difference for your argument.  
> **username_6**: The proofs actually show that you must have either $\Omega(n\log n)$ preprocessing or $\Omega(n)$ for each query. Of course both are tight. This shows that binary search and linear search are the only "interesting" search algorithms (at least in the classical world).  
> **username_9**: @Yuval: maybe you should write up this observation as an actual answer, because it seems to me that you have to do a moderate amount of work to get the above result from the proofs in the answers.  
> **username_9**: @Yuval: thinking about the proofs, I only see that you must have either $\Omega(n \log n)$ preprocessing or $\Omega(n^{1-\epsilon})$ query time for all $\epsilon$. It's possible to have $o(n \log n)$ preprocessing time and $O(n / \log n)$ query time. One can divide the list into $\log n$ lists of size $n/\log n$ each in time $\theta(n \log\log n)$ using repeated median-finding.  

---

### Answer by username_11 on 2017-09-19. Score: 0

As Peter Shor's answer notes, to rule out membership in a comparison-based model, we need to know how the element compares with every member. Thus, using $k0$, using $c \, n \log k$ preprocesssing, we cannot have $≤c \, n \log k/k$ query cost. This is optimal up to a constant factor since we can sort the data into $k' = k / \log k ≤ n/\log n$ approximately equal buckets (each bucket unsorted) in $O(n \log k') = O(n \log k)$ time, which allows $O(n/k')$ query cost.

In particular, using $O(n)$ preprocessing, we cannot have $o(n)$ query cost. Also, $o(n \log n)$ preprocessing corresponds to $k$ in $O(n^ε)$ for every $ε>0$ and thus $Ω(n^{1−ε})$ query cost.


---

