Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge).
I create many arbitrary subsets of U in running time (These sets may be or may not be sparse).
I do not need to check whether an element is in a set.
But I need to be able to
- check whether a set is empty,
- do the basic set operations difference and intersection, and
- calculate the cardinality of a set.
What is the most time-efficient data structure for this? It should be also space-efficient, if possible.
I have bit vector in my mind. Elements of U are numbered from 0 to n-1. Each of n bits represents the existence of the corresponding element.
- For k ≤ 5 or k ≤ 6 (depends on the computer architecture and the programming language) I can implement these sets as [unsigned] integers.
- But there will be a need for multi-word arithmetics in general case. So I believe, the space complexity of any set is ϴ(n) and time complexities of operations are ϴ(n) using bitwise operations and hamming weight.