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


eKo1 wrote:
There are two algorithms I can think of that determines whether n
numbers are distinct:

I want to prove that any algorithm A, in the worst-case, has to do at
least a number of comparison s proportional to n lg n. I've read that
this can be shown by reducing the problem to one of sorting but the
proof is bogus ....

Here's my attempt.

I'll assume that we can only access the data via pairwise comparisons.
Since the algorithm must work if all of the elements are distinct,
let's assume a[1] < a[2] < ... < a[n]. Any correct algorithm for
element distinctness must compare a[i] with a[i+1] for each i. If not,
then the algorithm would produce the same output if we changed a[i+1]
to a[i] (but this would change the answer from no duplicates to has
duplicates). The set of comparisons the algorithm uses forms a DAG,
with an edge from the smaller element in the comparison to the larger
element. Finding the total order (in linear time) yields the elements
in sorted order. Thus, any comparison-based algorithm for element
distinctness can be used for sorting n distinct elements, and the
standard n log n comparison-based sorting lower bound applies.

The most suspicious step of the proof is the one that begins "Any
correct algorithm".

.

Quantcast