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