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

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

2 Answers 2

Reset to default
-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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I try to find a lower bound for the worst case. Thank you $\endgroup$
    – ErroR
    Commented May 22, 2022 at 9:38
  • 2
    $\begingroup$ Please edit your question to include ALL the details of your request. $\endgroup$
    – Nathaniel
    Commented May 22, 2022 at 9:46
  • 1
    $\begingroup$ (I take computed address/index to be outside comparison computation model.) $\endgroup$
    – greybeard
    Commented May 23, 2022 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So if every element of B is found in A: How many comparisons were needed? $\endgroup$
    – greybeard
    Commented May 23, 2022 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$
    – Majid Zohrehbandian
    Commented May 23, 2022 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
    Commented May 23, 2022 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$
    – Majid Zohrehbandian
    Commented May 23, 2022 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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