A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets. enter image description here
This clearly generalizes. If we want to calculate the disjoint pieces, we have to compute 2ドル^n$ intersections, where $n$ is the number of sets.
However, if our sets were nested, i.e. $A_1 \subseteq A_2 \subseteq ... A_n$, we need only to compute $n$ intersections of the form $A_i \cap A_{i+1}^c$. The point is if we did our original exhaustive "binary search" computing 2ドル^n$ intersections we would find that most of these intersections are empty, so we are wasting computations.
My question is, what if we had $n$ sets where the vast majority are nested, but a few aren't and we don't know which. Can we compute an $O(n)$ number of intersections to find the disjoint pieces?
1 Answer 1
No, not $O(n)$. Suppose 0ドル.9n$ are nested and 0ドル.1n$ are not nested (and are unrelated). Then there can be at least 2ドル^{0.1n}$ different pieces, which is not $O(n)$.
You can find the nesting structure in $O(n^2)$ time by testing all pairs of sets to see which are subsets of the other.