# Algorithm to compute decomposition of a union of sets to a disjoint union of intersections

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.

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?

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.