0
$\begingroup$

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is both the time and space complexity of the naive algorithm that does this computation?

An inefficient recursive algorithm to do this task is:

enter image description here

Where

enter image description here

This results in Θ(2n) exponential blow up time complexity and this is incredibly bad!

Another iterative algorithm to compute the cardinality is:

enter image description here

This formula was taken from this proof wiki webpage, although it doesn't show any proof, but only the formula itself.

But I don't know how to analysis it's both time and space complexity.

EDIT: It appears that the iterative algorithm, unlike the recursive algorithm, iterates over all the different subsets of {S1, ... , Sn} in order to compute the cardinality of the union of all sets from S1 to Sn, but the number of subsets of {S1, ... , Sn} is 2n, so the time complexity of the iterative algorithm is same as the time complexity of the recursive algorithm, i.e. the time complexity of the iterative algorithm is also Θ(2n) exponential time blow up as the time complexity of the recursive algorithm.

Does exist polynomial both time and space algorithm to compute this?

I tried to google an answer to this question for hours, but I didn't find it anywhere.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ When you ask about time or space complexity of an algorithm you should explicitly specify what input is and what you want to compute. In your case it is clear that you want compute unions of sets. But what are these sets? Are they given to algorithm as inputs? If so, how are they represented in the memory (binary tree, linear array, ...)? Does your algorithm build the union itself? $\endgroup$
    – fade2black
    Commented Jul 23, 2017 at 5:01
  • 1
    $\begingroup$ Also, what is "small set"? How small are they? both 1 element and 100000 element sets may be considered as "small". Exact definition of a "small set" would be helpful. Please check disjoint-set data structure. $\endgroup$
    – fade2black
    Commented Jul 23, 2017 at 5:09
  • $\begingroup$ The sets are not pairwise disjoint, and we can choose whatever we want each set to be. Let's assume that all sets are hash tables and the cardinality of each set is equals to k, where k is in the algorithm's input and the sets, obviously, are in the algorithm's input as well. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 23, 2017 at 9:05

1 Answer 1

Reset to default
2
$\begingroup$

Yes, there is a polynomial time algorithm. You simply iterate over all of the elements of each set and add each one to some data structure (e.g., a hashtable, a balanced binary tree) if it's not already present. Then, you count the number of items in that data structure.

If there are $n$ input sets $S_1,\dots,S_n$, each of size $k$, then the running time of this is $O(nk \log(nk))$ if you use a self-balancing binary tree data structure. The expected running time is $O(nk)$ if you use a hash table. The size of the input is $\Theta(nk)$, so this yields an algorithm whose running time is polynomial in the size of the input.

Improve this answer
$\endgroup$
4
  • $\begingroup$ And are you sure that this algorithm is correct? Does this algorithm really returns the cardinality of the union of all sets? Note that the sets aren't pairwise disjoint. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 23, 2017 at 16:27
  • $\begingroup$ @ErezZrihen, yes, and yes. Pairwise disjointness is not required; see the clause "if it's not already present". $\endgroup$
    – D.W. ♦
    Commented Jul 23, 2017 at 16:35
  • $\begingroup$ I have noticed. And what is the complexity of computing the cardinality of the union of regular expressions without kleene star closure, where each regular expression is only concatenation of 0, 1 and Sigma, where Sigma=0+1? I think this is EXPTIME problem. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 23, 2017 at 16:39
  • $\begingroup$ I know that this is a new question, so I will ask it as a new question, not as comment. $\endgroup$
    – Farewell Stack Exchange
    Commented Jul 23, 2017 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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