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.

  • 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.” – Tsuyoshi Ito Aug 18 '11 at 12:32
  • 2
    (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 Aug 18 '11 at 12:54
  • 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. – Tsuyoshi Ito Aug 18 '11 at 12:56
  • 6
    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 Aug 18 '11 at 13:11
  • 2
    @Filip: Is that easy to see? If it is true, then I agree that it solves the question. – Tsuyoshi Ito Aug 18 '11 at 13:29
up vote 30 down vote accepted

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.

  • 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 Aug 21 '11 at 13:17
  • (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 Aug 21 '11 at 13:17
  • 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 Aug 21 '11 at 17:40
  • 5
    @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 Aug 21 '11 at 18:48
  • 1
    @Aryabhata: it does. What is the $O(\log^2 n)$ algorithm? – Peter Shor Aug 23 '11 at 19:08

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.

  • 1
    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 Aug 23 '11 at 20:49
  • 8
    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 Aug 23 '11 at 23:08
  • 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). – Yuval Filmus Aug 26 '11 at 15:12
  • 1
    @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 Aug 31 '11 at 1:05
  • 1
    @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 Sep 19 '11 at 21:26

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

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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