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

Ralph Hartley wrote:
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,

That should have been O(n log n)

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

However, for the original problem there is no need to look at an array
element unless it is indexed by one of the input data elements, so it
has time complexity O(n) rather than O(k+n). The space complexity
is still O(k).

Patricia
.