# Lower bound union of a unsorted array with sorted array

Suppose given two Arrays $$A$$ that is sorted array with length $$n$$ and $$B$$ unsorted array with length $$n$$. We want to find union of two arrays (i.e. we try to compute $$A\cup B$$) with comparison computation model. Can we claim that the lower bound of this problem is $$\Omega(n\log n)$$?

• I suppose you want the resulting array to be sorted? May 22 at 9:31
• No, I want just compute $A\cup B$. May 22 at 9:31
• So you want an array of elements that appear in $A$ or in $B$, without duplicates? May 22 at 9:33
• According to union definition, yes. May 22 at 9:34
• Since $A$ and $B$ are not sets but arrays, it is not obvious, for example $A$ or $B$ could already contain duplicates. Mathematical notations and their use in computer science are not always clears, that's why you have to be precise in what you ask from the start. May 22 at 9:44

I think this is possible in $$\mathcal{O}(n)$$ average case, using hashtables.

You just need to create a hashtable of your elements, and before adding a new one to the result, you can check in $$\mathcal{O}(1)$$ average if it is already present, and add it to the hashtable if not.

I suppose here that a comparison between two elements is done in $$\mathcal{O}(1)$$ time.

• I try to find a lower bound for the worst case. Thank you May 22 at 9:38
• Please edit your question to include ALL the details of your request. May 22 at 9:46
• (I take computed address/index to be outside comparison computation model.) May 23 at 5:13

But I think this is possible in $$O(n(log(n)))$$. Since, you can set C=A (suppose that we have no duplicate in A) and then for addition of each member from B to C it is sufficient to search it in sorted array A and if it was not in A then add the member to C.

• So if every element of B is found in A: How many comparisons were needed? May 23 at 4:04
• For each element of B we have at most $log(n)$ comparisons to know that the member is not in A. Then we have $O(n(log(n)))$. May 23 at 4:30
• Now what is the But in Can we claim [this problem is in] Ω(nlogn)? and I think [finding the union of two arrays of length n] is possible in O(n(log(n)))? May 23 at 4:34
• $\Omega(n(log(n))$ means that execution of the algorithm is more than some constant multiple of $n(log(n)$ but I said that execution of the algorithm is less than some constant multiple of $n(log(n)$ and this means $O(n(log(n))$ complexity. May 23 at 5:10