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.

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.

StackExchange Computer Science Q#28237, answer score: 7