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

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:

Where

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

Another iterative algorithm to compute the cardinality is:

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.

• 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? – fade2black Jul 23 '17 at 5:01
• 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. – fade2black Jul 23 '17 at 5:09
• 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. – Farewell Stack Exchange Jul 23 '17 at 9:05

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.