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

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. (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.)

Tor Myklebust
.