[Solved]: Computing the complement of a set

Problem Detail: 

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.

Asked By : Kiyal M.

Answered By : babou

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.

Your own answer was good because of that. Only your complexity assessment was wrong.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28237

3.2K people like this

 Download Related Notes/Documents