# What is the time complexity of subset testing?

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?

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

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.
• 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$. – SomeName Jun 14 '20 at 14:26
• 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? – Steven Jun 14 '20 at 14:28
• While this is not a definitive answer, I do not expect to get a better one, so I've marked it as accepted. – SomeName Jun 14 '20 at 14:34
• 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. – SomeName Jun 14 '20 at 14:42