# complexity of outputting the union of a collection of subsets of a set

This question concerns the time complexity of outputting the unions of subsets of a given set.

Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with respect to $m+k$? Or $(m+k)p(\log (m+k))$, where $p(x)$ is some polynomial? Or at least known is there a subquadratic algorithm (with respect to $m+k$)?

Any direction on this would be much appreciated.

• Note the input size may be $\Theta(mk)$. – xskxzr Jul 6 '18 at 3:26
• Thanks! Silly oversight on my part, and grateful for having it pointed out. I'd like to re-ask the question, but this time with input size the number of elements in the – Steven48 Jul 6 '18 at 17:31
• correction: the size of the input should have been the sum of the number of elements over the m given subsets. So m_1, ..., m_k are the sizes of the first, second, k th subset respectively, then the input size is m_1+ ...+ m_k.. Apologies---just getting used to website. Thanks again.. -Steve – Steven48 Jul 6 '18 at 17:42

That's not possible. Any correct algorithm will have to read all of the input. The input size is $\Theta(mk)$, so that means any correct algorithm will have to have running time at least $\Omega(mk)$. $O(m+k)$ and $O(m+k) p(\log(m+k)))$ are not achievable.