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 &Theta;(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 &Theta;(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.
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.