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


eKo1 wrote:
Googmeister 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.

Thinking about decision trees reminded me of the typical coin-weighing
problems, which in turn gave me an idea: I can rephrase my original
post as a coin-weighing problem.

Suppose you have n coins, all of which look exactly the same. You are
given a balance scale and are asked to determine if the coins are all
distinct, i.e. they all weigh differently. What is the minimum amount
of times the balance will be used to solve the problem?

The coin weighing problem is slightly different than your original
problem, since, presumably, you can put multiple coins on either side
of the scale. The Ben-Or result implies that you still need at least
Omega(n log n) comparisons for this problem.

.

Relevant Pages

  • Re: On the complexity of determining whether n numbers are distinct
    ... element distinctness problem. ... Thinking about decision trees reminded me of the typical coin-weighing ... Suppose you have n coins, all of which look exactly the same. ... given a balance scale and are asked to determine if the coins are all ...
    (comp.theory)
  • Re: On the complexity of determining whether n numbers are distinct
    ... so the Ben-Or result applies to your problem. ... Thinking about decision trees reminded me of the typical coin-weighing ... Suppose you have n coins, all of which look exactly the same. ... given a balance scale and are asked to determine if the coins are all ...
    (comp.theory)