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

Markus Triska wrote:
"eKo1" <berndlosert@xxxxxxxxxxxx> writes:

example?

Say multiset of numbers is {1,2,3,1}. Initially, bitvector is:

... 0 0 0 0 0

First number is 1, so we set bit one in the bitvector:

... 0 0 0 1 0

Next number: 2; we (also) set bit two:

... 0 0 1 1 0


Next number (i.e., 3):

... 0 1 1 1 0

Next number is 1, and bit one is already set => numbers non-distinct.

Incidentally, the minimum number of comparisons for a sort also breaks
down if you can use the elements to index an array. Proofs of it depend
on the requirement that the only operation on the elements is pairwise
comparison.

Consider an array of integers, and increment vector element n by one for
each n in the input:

Initially, the vector is:

.... 0 0 0 0 0

First number is 1, so we increment element 1:

.... 0 0 0 1 0

Next number: 2; we increment element two:

.... 0 0 1 1 0


Next number (i.e., 3):

.... 0 1 1 1 0

Next number is 1, so increment element 1 again:

.... 0 1 1 2 0

Now iterate through the vector in increasing index order. If element i
is k, write i out k times:

1 1 2 3

and the original data is sorted in O(n) operations, with no pairwise
comparisons.

Patricia
.