If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:
U1 = {1,2}
U2 = {3,4,5}
C1 = {3,5}
C2 = {2}
The above sets are guaranteed to be subsets of S, however they may not be subsets of each other. To check if C1 is subset of U2 I need to iterate through both sets and check if all elements of C1 are in U2. In this case 3 and 5 are elements of U2 thus C1 is a subset of U2.
But this operation is O(n) at best if you keep everything sorted. I'm wondering, is it possible to select the elements of S wisely or construct a data structure in such a way to perform fast (like O(1)) subset check operations ?
If this means I need to look into parallel algorithms I am open to that as well.