What is the time complexity of subset testing?

Question

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?

Answer 1

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.