constant-time set operations

Question

Are there constant-time algorithms for binary set intersection and union?

I imagine using bitmaps with pointers to elements in the memory and using OR for union and AND for intersection.

Does anyone now of a solution?

Answer 1

It is constant time up to 32 elements with the BitArray class. You could write a custom one to get up to 64 elements, using an underlying ulong[]. Unmanaged code makes 128 elements possible with the _mm_or_si128 and _mm_and_si128 intrinsics. Hard to use due to their memory alignment requirements, can't get that from the garbage collected heap.

These are not practical amounts in most any case where you'd want to optimize this kind of code. It is fundamentally an O(n) algorithm with a very small Oh. Might as well use BitArray.