# Set intersection using bloom intersection

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?

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.