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


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

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?

Yes, you use bitwise-and and shift-right and indexing and so forth. If
we can only do arithmetic and make decisions only using comparisons, I
suppose I can fully believe that Ben-Or's result works here. But we
have more power than algebraic decision trees do if our inputs are
integers.

Right, the Ben-Or result does not apply if fancier operations are
allowed, e.g., using the data as an index into an array. The OP was
asking about comparison-based algorithms.

.

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)
  • Re: On the complexity of determining whether n numbers are distinct
    ... I want to prove that any algorithm A, in the worst-case, has to do at ... this can be shown by reducing the problem to one of sorting but the ... log n lower bound in the algebraic decision tree model of computation. ... I didn't know that the lower-bound was dependent on the model of ...
    (comp.theory)
  • Re: Training Decision Tree
    ... decision tree and one for its evaluation. ... I want to use these two in SQL Server so I can compare the ... C4.5 algorithm with the decision tree algorithm of SQL Server(using ... First i created a mining structure using the test data set. ...
    (microsoft.public.sqlserver.datamining)
  • Re: Training Decision Tree
    ... decision tree and one for its evaluation. ... I want to use these two in SQL Server so I can compare the ... C4.5 algorithm with the decision tree algorithm of SQL Server(using ... entropy because C4.5 is an entropy based classifier). ...
    (microsoft.public.sqlserver.datamining)