1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Note the input size may be $\Theta(mk)$. $\endgroup$ – xskxzr Jul 6 '18 at 3:26
  • $\begingroup$ 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 $\endgroup$ – Steven48 Jul 6 '18 at 17:31
  • $\begingroup$ 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 $\endgroup$ – Steven48 Jul 6 '18 at 17:42
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! If I change the input size to the sum of the sizes (cardinalities) of the m given subsets, would there be an x log x time or something similar, where x is the size of input? Sorry for taking your time---just getting used to the web site. Thanks again, Steve $\endgroup$ – Steven48 Jul 6 '18 at 18:11
  • $\begingroup$ @Steven48, I don't know. if you change the question, the answer might change. There are many ways you might change the problem specification that might affect the input size. Without understanding what modified question you had in mind, I'm not in a position to answer it. Perhaps you might like to ask a new question once you have figured out how to formulate in a careful way and spent some time trying to answer it on your own. $\endgroup$ – D.W.♦ Jul 6 '18 at 18:19

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.