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


goanna wrote:
Technically correct, perhaps, but all a bit silly really.
You've just replaced pairwise comparisons with increments,
comparisons to zero, and decrements, which all still need
to be counted. As your vector needs to be as large as the
largest number k, which may be very much larger than n,
the number of comparisons to zero may be much larger than
the number of pairwise comparisons you've eliminated.

Yes, that is very true. I didn't think of that. So the time complexity
is now bounded by the size of the vector which is the size of the
largest number k rather than by n.

.