0
$\begingroup$

Consider the following problem:

Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted. Given as inputs the strings $a_1,...,a_n$ and $b_1,...,b_m$, determine if $A \subseteq B$.

What is the time complexity of this problem?

$\endgroup$
4
  • $\begingroup$ Would the question change if the sets were allowed to range over some arbitrary set? $\endgroup$ – SomeName Jun 14 '20 at 14:02
  • $\begingroup$ You can do it in order $(n+m) \log \min(n,m)$. $\endgroup$ – Yuval Filmus Jun 14 '20 at 14:07
  • $\begingroup$ @YuvalFilmus You sort one set and then do binary search? $\endgroup$ – SomeName Jun 14 '20 at 14:10
  • $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus Jun 14 '20 at 16:14
2
$\begingroup$

Since you talk about sets I assume that there are no duplicates.

You can assume $n \le m$ otherwise you can answer "no" in time $O(1)$. You can further assume $\max_{a \in A} a \le \max_{b \in B} b$, otherwise the answer is again "no", and can be found in time $O(\min\{m, U\})$, where $U = \max_{a \in A} a$.

Your problem can be solved in $O(\min\{m \log n, U\})$ worst-case time. To do so use the best of the following two strategies:

  • Sort $A$. Keep a counter $x$ of how many elements from $B$ have been found in $A$. Initially $x=0$. For each element of $b \in B$ (in arbitrary order), determine whether $b \in A$ using a binary search. If $b \in A$ increment $x$. After all elements of $B$ have been examined, return true if and only if $x=n$.
  • Keep an array $X[0, \dots, U]$ of $U+1$ boolean elements. Initially all the elements of $X$ are false. For each element $b \in B$, check if $b \le U$ and if that is the case set $X[b]$ to true. Iterate over the elements $a \in A$ and check whether $X[a]$ is true for all of them. If this is the case return true, otherwise return false.

Notice that $\Omega(m \log n)$ is a lower bound on the worst-case time complexity needed to solve your problem (as a function of $m$ and $n$) in the algebraic computation tree model. See Corollary 3 on page 147 (155 of the pdf file) here.

You can also solve your problem in $O(m)$ expected time by using a hashset $H$:

  • Insert all the elements of $B$ into $H$. This takes $O(1)$ expected time per insert operation, i.e., $O(m)$ time in total.
  • For each element $a \in A$, check whether $a \in H$. This takes $O(1)$ expected time per check.
$\endgroup$
4
  • $\begingroup$ Thank you for your great answer. But wouldn't it be faster to use a disjoint-set data structure? I thought one could first put $B$ in the disjoint set data structure and then search for every element of $A$ in $B$. $\endgroup$ – SomeName Jun 14 '20 at 14:26
  • $\begingroup$ That would cost you $O(U)$ just to build the disjoint-set data structure. Plus, what's the advantage of using a disjoint-set data structure if you never perform any union operation? $\endgroup$ – Steven Jun 14 '20 at 14:28
  • $\begingroup$ While this is not a definitive answer, I do not expect to get a better one, so I've marked it as accepted. $\endgroup$ – SomeName Jun 14 '20 at 14:34
  • $\begingroup$ I've changed my mind, considering that there are algorithms for sorting better than n log n, somebody might even know about a better algorithm right now. $\endgroup$ – SomeName Jun 14 '20 at 14:42

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.