- To generate a list of size $n$,
- Containing unique integers,
- Sampled uniformly in the range $\left[0,m\right)$,
- In $O(n)$ time, except that:
- Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.
Apologies if this is a duplicate, if you find one, feel free to point it out.
EDIT: to clarify, the question implies that we are concerned the complixity in terms of bit-operations. (See logarithmic cost model).