Re: On the complexity of determining whether n numbers are distinct
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 26 Sep 2006 21:46:31 -0700
eKo1 wrote:
eKo1 wrote:
eKo1 wrote:
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?
If I weigh two coins at a time, the decision tree for this problem will
have a height h = C(n, 2) so in the worse case, the balance would be
used C(n, 2) times which is proportional to n^2. This is certainly not
n lg n. Hmm....
Nevermind. Every time I weigh two coins, say a and b, either a > b, a <
b or a = b. That means each internal node in the decision tree has 3
children.
I drew a decision tree for n = 3 for this problem and a decision tree
for sorting n = 3 numbers and they look exactly the same except that
the internal nodes on the sorting decision tree only have two children
as opposed to three. I must figure out a way to show that both trees
have the same height. Perhaps a proof by induction is in order. I'll
think about this a bit and post some results tomorrow.
Let T be the decision tree used to solve the sorting problem. Form T'
from T by doing the following: for each internal vertex, add an extra
child in the middle that represents a weighing were the two coins
weighed the same. T' is the decision tree for the distinct-coin problem
where the terminal vertices that are left or right children represent
that the coins are distinct and the terminal vertices that are middle
children represent that the coins are not distinct. Hence, sorting and
element-distinctness have the same lower-bound time complexity.
Is this a valid argument?
.
- References:
- On the complexity of determining whether n numbers are distinct
- From: eKo1
- Re: On the complexity of determining whether n numbers are distinct
- From: Googmeister
- Re: On the complexity of determining whether n numbers are distinct
- From: eKo1
- Re: On the complexity of determining whether n numbers are distinct
- From: Googmeister
- Re: On the complexity of determining whether n numbers are distinct
- From: eKo1
- Re: On the complexity of determining whether n numbers are distinct
- From: eKo1
- Re: On the complexity of determining whether n numbers are distinct
- From: eKo1
- On the complexity of determining whether n numbers are distinct
- Prev by Date: Gray Code
- Next by Date: Re: On the complexity of determining whether n numbers are distinct
- Previous by thread: Re: On the complexity of determining whether n numbers are distinct
- Next by thread: Re: On the complexity of determining whether n numbers are distinct
- Index(es):
Relevant Pages
|
