1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ I suppose you want the resulting array to be sorted? $\endgroup$
    – Nathaniel
    May 22 at 9:31
  • $\begingroup$ No, I want just compute $A\cup B$. $\endgroup$
    – ErroR
    May 22 at 9:31
  • $\begingroup$ So you want an array of elements that appear in $A$ or in $B$, without duplicates? $\endgroup$
    – Nathaniel
    May 22 at 9:33
  • $\begingroup$ According to union definition, yes. $\endgroup$
    – ErroR
    May 22 at 9:34
  • 3
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    May 22 at 9:44

2 Answers 2

-1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I try to find a lower bound for the worst case. Thank you $\endgroup$
    – ErroR
    May 22 at 9:38
  • 2
    $\begingroup$ Please edit your question to include ALL the details of your request. $\endgroup$
    – Nathaniel
    May 22 at 9:46
  • 1
    $\begingroup$ (I take computed address/index to be outside comparison computation model.) $\endgroup$
    – greybeard
    May 23 at 5:13
-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So if every element of B is found in A: How many comparisons were needed? $\endgroup$
    – greybeard
    May 23 at 4:04
  • $\begingroup$ 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)))$. $\endgroup$ May 23 at 4:30
  • $\begingroup$ 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)))? $\endgroup$
    – greybeard
    May 23 at 4:34
  • $\begingroup$ $\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. $\endgroup$ May 23 at 5:10

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.