9
$\begingroup$

Consider the following problem:

Input: lists $X,Y$ of integers

Goal: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$. Is there a deterministic, linear-time algorithm for this problem? In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.


I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable. The expected running time will be $O(n)$. However, I can't see how to find a deterministic algorithm with $O(n)$ running time. If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time. The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time. Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation. I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.

$\endgroup$
  • $\begingroup$ Hashtables are O(n log n) as you need to handle collisions. $\endgroup$ – Thorbjørn Ravn Andersen Feb 5 '15 at 0:45
  • 1
    $\begingroup$ @ThorbjørnRavnAndersen, I'm not seeing where you are getting that from. Using 2-universal hash functions and a suitably-sized hash table ensures that the number of hash collisions is minimal (with high probability), so I believe $O(n)$ running time is achievable. I'm not sure where you got $O(n \lg n)$ from; if you don't do something special (like use 2-universal hashing), the worst case is $O(n^2)$, due to collisions. $\endgroup$ – D.W. Feb 5 '15 at 1:12
  • $\begingroup$ The devil is in the detail, here a "suitably sized hash-table". This might turn out to be pretty big, if you do not want collisions. The typical n-log-n is (if I recall correctly) for handling the hash function collisions with a list. $\endgroup$ – Thorbjørn Ravn Andersen Feb 5 '15 at 1:16
  • 1
    $\begingroup$ @ThorbjørnRavnAndersen The expected number of keys mapping to the same address is constant (for tables that are not overloaded), so the kind of collision resolution is irrelevant. See also here. $O(n \log n)$ fits the worst case if you use (external) balanced BSTs instead of lists. $\endgroup$ – Raphael Feb 5 '15 at 7:33
1
$\begingroup$

You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y. This does not impose any restrictions of the ordering of X and Y.

  1. Initially all bits are unset.
  2. Iterate over X setting the corresponding bit.
  3. Iterate over Y checking if the corresponding bit was set above.
$\endgroup$
  • 2
    $\begingroup$ Unfortunately, you cannot assume that all of the integers are small (you can't assume they are small enough that this algorithm will work). In the general case, the running time of this algorithm will be exponential in the bit-length of the list elements. Thank you, though! $\endgroup$ – D.W. Feb 5 '15 at 1:11
  • $\begingroup$ Let's name it a "suitably sized bit-array" then. Also linear in the bit-length is equivalent to log-n. Are you serious about getting log-n performance without any restrictions or preconditions on the input data? $\endgroup$ – Thorbjørn Ravn Andersen Feb 5 '15 at 1:19
  • 2
    $\begingroup$ @ThorbjørnRavnAndersen The space is exponential in the bit length (you need to map from all possible values), and the time is linear in the total list size (you need to look at all values in both lists). Nothing is linear in the bit-length. $\endgroup$ – wchargin Feb 5 '15 at 3:36
0
$\begingroup$

Since you are saying that the two lists contain integers, I guess we can run a radix sort on the two lists and then do a linear search comparing the two lists for equivalent items.

$\endgroup$
  • 4
    $\begingroup$ This only works if there is a bound on the magnitude of the numbers. $\endgroup$ – Luke Mathieson Feb 5 '15 at 6:36
  • $\begingroup$ but I thought high magnitude will be a problem only for counting sort and for radix sort we can select a high enough radix to solve that problem... please let me know what I'm missing here $\endgroup$ – anirudh Feb 5 '15 at 9:54
  • $\begingroup$ What if one of the numbers is 2^(2^128)? $\endgroup$ – miniBill Feb 5 '15 at 21:13
  • $\begingroup$ @anirudh but then you have a different algorithm for different input sizes - you need a bigger alphabet each time you increase the radix, you're just exporting the complexity of increasing magnitude to increasing the alphabet size. Of course this is only possible in theory as well, I don't think a lot of hardware allows you to change which base it represents numbers in (we can pretend at the input and output ends, but it boils down to (mostly) binary). $\endgroup$ – Luke Mathieson Feb 5 '15 at 23:43
0
$\begingroup$

Why not insert the integers of each list into a simple bitwise trie? Would this not be optimal, in the sense that it is $\mathcal O\left(n\cdot \overline m\right)$, where $\overline m$ is the average bit size of the integers; specifically, I do not see how you can do better, as simply *reading* the two lists would take this amount of time.

$\endgroup$
  • $\begingroup$ Thanks for your note. See the last paragraph of the question, which addresses this point. In the RAM model, you can read the two lists in $O(n)$ time -- it doesn't take $O(n \cdot \overbar{m})$ time. So that's where the model of computation comes into it -- this answer doesn't actually prove that deterministic linear time is impossible. $\endgroup$ – D.W. Apr 13 '16 at 19:23
  • $\begingroup$ @D.W. In the RAM model, there is a word size $w$ which is a constant, and it bounds $m$ and thus also $\overline{m}$, which results in a runtime of $\mathcal O\left(n\right)$, or am I mistaken? $\endgroup$ – Realz Slaw Apr 13 '16 at 19:28
  • $\begingroup$ hmm maybe considering $w$ a constant is a mistake. $\endgroup$ – Realz Slaw Apr 13 '16 at 19:32
  • $\begingroup$ ($w$ is not considered constant, but dependant on $n$: you can have it any constant multiple $m$ of what is necessary to represent $n$ (wide enough to represent $n^m$), just not arbitrarily large.) $\endgroup$ – greybeard Apr 14 '16 at 4:45
-1
$\begingroup$

It is similar to the Elemet Uniqueness problem, where you have a set of n numbers and you want to determine whether all of the elements are distinct. The problem has an algebraic computation tree lower bound of $O(n\log n)$.

$\endgroup$
  • 1
    $\begingroup$ The question is quite explicit about linear deterministic time, not log-linear. Also to determine if (not on what value) set has only unique elements you can do faster than loglinear. $\endgroup$ – Evil Apr 13 '16 at 18:16
  • 1
    $\begingroup$ Do you mean $\Omega(n\log n)$? If so, that might suggest that the problem in the question can't be solved in linear time. But just saying that a related problem can be solved in log-linear time doesn't really answer the question. (cc @EvilJS) $\endgroup$ – David Richerby Apr 13 '16 at 19:06
  • 1
    $\begingroup$ Thanks for your note. I wonder if you missed the last sentence of the question. I'll repeat it here: "I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model." In other words, this answer doesn't answer the question; it merely repeats something that I already said in the question I was aware of, but which doesn't resolve the question. $\endgroup$ – D.W. Apr 13 '16 at 19:24
  • $\begingroup$ It can be done in $O(n \log \log n)$ time which is better than given $O(n \log n)$, so I am sure this was not $\Omega(n \log n)$, but this does not solve the D.W. question. So just comment here. $\endgroup$ – Evil Apr 13 '16 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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