Lower bound union of a unsorted array with sorted array

Question

I read this link and I have similar question.

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

• Nathaniel: I suppose you want the resulting array to be sorted?
• ErroR: No, I want just compute $A\cup B$.
• Nathaniel: So you want an array of elements that appear in $A$ or in $B,ドル without duplicates?
• ErroR: According to union definition, yes.
• Nathaniel: 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.

Answer 1

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.

• ErroR: I try to find a lower bound for the worst case. Thank you
• Nathaniel: Please edit your question to include ALL the details of your request.
• greybeard: (I take computed address/index to be outside comparison computation model.)

Answer 2

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.

• greybeard: So if every element of B is found in A: How many comparisons were needed?
• Majid Zohrehbandian: 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)))$.
• greybeard: 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)))?
• Majid Zohrehbandian: $\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.