# Can element uniqueness be solved in deterministic linear time?

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.

• Hashtables are O(n log n) as you need to handle collisions. Feb 5, 2015 at 0:45
• @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.
– D.W.
Feb 5, 2015 at 1:12
• 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. Feb 5, 2015 at 1:16
• @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.
– Raphael
Feb 5, 2015 at 7:33

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.
• 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!
– D.W.
Feb 5, 2015 at 1:11
• 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? Feb 5, 2015 at 1:19
• @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. Feb 5, 2015 at 3:36

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.

• This only works if there is a bound on the magnitude of the numbers. Feb 5, 2015 at 6:36
• 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 Feb 5, 2015 at 9:54
• What if one of the numbers is 2^(2^128)? Feb 5, 2015 at 21:13
• @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). Feb 5, 2015 at 23:43

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.

• 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.
– D.W.
Apr 13, 2016 at 19:23
• @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? Apr 13, 2016 at 19:28
• hmm maybe considering $w$ a constant is a mistake. Apr 13, 2016 at 19:32
• ($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.) Apr 14, 2016 at 4:45

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

• 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.
– Evil
Apr 13, 2016 at 18:16
• 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) Apr 13, 2016 at 19:06
• 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.
– D.W.
Apr 13, 2016 at 19:24
• 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.
– Evil
Apr 13, 2016 at 22:50