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


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?

.

Relevant Pages

  • 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)
  • 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)