Re: On the complexity of determining whether n numbers are distinct

Patricia Shanahan wrote:
Agreed. It is very silly. It has the same complexity as a good pairwise
comparison sort if k is O(log n). I would only use it if k were small,
and smaller than n. For example, sorting thousands of 8 bit bytes.

For the original problem, it is sillier than that!

If k (the largest number) is smaller than n-1, then n numbers can *never* be distinct.

Ralph Hartley
.