1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.