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


Tor Myklebust wrote:
Googmeister <googmeister@xxxxxxxxx> wrote:

Decision trees are a model of computation. Algebraic decision trees are
more general, so the Ben-Or result applies to your problem. That is,
any comparison-based algorithm (can only access the data through
pairwise comparisons) requires Omega(n log n) comparisons to solve the
element distinctness problem.

I thought that the Ben-Or result applied only to the sorting of real
numbers.

That,s right. But I think it also generalizes the decision tree model
because if you can only access the data via pairwise comparisons, your
algorithm might as well pretend the inputs are real numbers. Of course,
the n log n element distinctness lower bound was known in the decision
tree model of computation before Ben-Or.

(In particular, I believe there is an
O(n log(n) / logloglog(n)) algorithm for sorting a list of n integers,
using a logloglog(n)-way search tree.)

I assume this algorithm accesses the data via operations other than
pairwise comparisons. If you can only access the data via pairwise
comparisons, how could you exploit the fact that the inputs are
integers?

.

Relevant Pages

  • Re: On the complexity of determining whether n numbers are distinct
    ... pairwise comparisons) requires Omegacomparisons to solve the ... I thought that the Ben-Or result applied only to the sorting of real ... But I think it also generalizes the decision tree model ... algorithm might as well pretend the inputs are real numbers. ...
    (comp.theory)
  • Re: On the complexity of determining whether n numbers are distinct
    ... pairwise comparisons) requires Omegacomparisons to solve the ... I thought that the Ben-Or result applied only to the sorting of real ... But I think it also generalizes the decision tree model ... algorithm might as well pretend the inputs are real numbers. ...
    (comp.theory)