# Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in $\{1, \ldots, n\}$ but not in $A$.

One way to do this is to sort the entries of $A$ and then go through them and list all the entries I do not see. This takes $O(n \log n)$ in the unit cost RAM model. My question is whether there exists a linear time $O(n)$ algorithm in the same model.

• Actually, the sorting can be faster than that; see these four papers. $\;$ – user12859 Jul 5 '14 at 22:57

Since you have both lists, even if not both at the same time, your space cost is at least that of the longest, thus at least $n/2$. This corresponds to a $O(n)$ space complexity.

So, unless you exclude it for some reason, it makes sense to use a bit array $M[1:n]$ to represent the set A by its characteristic function, i.e. $M[i]=0$ iff $i\notin A$, and $1$ otherwise. The space complexity is unchanged, and the array $M$ is actually much smaller than one of the two lists (initial or final).

Initializing the array $M$ from the initial list is linear.

Then you can take the logical complement of the array $M$ in linear time.

Then you scan the array in linear time to get all the element of the complement of your initial list in linear time $O(n)$

Of course, by now you have noticed your mistake: sorting is in time $O(n \log n)$ (or better according to comment) when $n$ is the number of element to be sorted. But it is trivially linear if $n$ is the size of the finite ordered set they come from.

Using an array, as I just did is one way of sorting in linear time with respect to the size of the referance set.