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

"eKo1" <berndlosert@xxxxxxxxxxxx> writes:

I want to prove that any algorithm A, in the worst-case, has to do at

Maintain a bit-vector, initially set to 0. For each number n, check
whether n-th bit is set (if yes => non-distinct). Otherwise, set n-th
bit and continue. Requires no comparison between any of the numbers.

Best wishes,
Markus Triska
.

Quantcast