Newsgroups: sci.math
From: hoey@ai.etl.army.mil (Dan Hoey)
Date: 29 Mar 90 00:09:41 GMT
Subject: Re: Determining whether n numbers are distinct

gor...@cs.tamu.edu (Dan Gordon) writes:

>>Given n numbers (real or integer), we want to determine whether they
>>are distinct.  Can this problem be solved in O(n) time?

>This problem is known as the element uniqueness problem and it can't be done
>in less than order nlogn time ... if you are only allowed to do comparisons.
>If your numbers are integers in the range 1 to M, then you can solve the
>problem in O(M) time. More generally, you can use hashing techniques too.

In fact, on a RAM model of computation, where you can do indexing into
arbitrarily large arrays in constant time, there is a fast algorithm
for arbitrary numbers.  It may be a real ram with floor, and you
determine element uniqeness for real numbers.  I read it in 1978 or
79, probably in JACM or CACM.

Dan