1
$\begingroup$

Let $A \subseteq Z$, where $Z=\{1,2,3,\cdots,n\}$. Now given any $B \subseteq Z$, we need to check whether $A \cap B =\varphi$ or not. I am looking for a randomized algorithm.

I am trying to implement it using a bloom filter. Create a bloom filter for $A$ and $B$ respectively. Now consider the intersection of $A$ and $B$ which means AND operation of $A$ and $B$. Assume that there are $n$ elements in both arrays. Then the number of bits required in bloom filters will be $O(n)$ many bits and $O(n/\log n)$ many words. AND operation is going to take $O(n/\log n)$ time

Is there any better (faster runtime) algorithm for the above problem?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Without any special knowledge about the distribution of data, you cannot do better than that. In the worst case, you have to read every element of $B$. There can be $\Theta(n)$ elements of $B$. So, every correct algorithm must take at least $\Omega(n/\log n)$ time in the transdichotomous model, where you can read an entire $O(\log n)$-size word in 1 step.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. I was looking for an algorithm which can give the result with high probability. $\endgroup$
    – Rma
    Nov 15, 2022 at 6:00

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.