1
$\begingroup$

I have the following problem:

You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of the scale and see which collection is heavier.

Goal is to find the heavier object, with the minimum number of weigh.

I know the best algorithm that can solve this problem. Here is the pseudocode:

function findDiffWeight(L[1:n]){

   if(L.size == 1) return L[1]

   int x = sum(L[1 : n/2])
   int y = sum(L[n/2+1 : n])

   if(x>y)  call findDiffWeight(L[1 : n/2])
   if(y>x)  call findDiffWeight(L[n/2+1 : n])
}

But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than logn operations.

However how to prove it? Could you give me some idea about finding lower bound for this problem?

$\endgroup$
  • 2
    $\begingroup$ Are you familiar with the proof that sorting has a $\Omega(n \log n)$ lower bound? A similar principle applies here. $\endgroup$ – Tom van der Zanden Jan 1 '15 at 17:46
  • $\begingroup$ @TomvanderZanden This will only give $\log_3 n$ rather than $\log_2 n$, since we could also have equality. $\endgroup$ – Yuval Filmus Jan 2 '15 at 9:36
3
$\begingroup$

Your algorithm, which requires $\lceil \log_2 n \rceil$ weighings, is in fact not optimal. This paper proposes an algorithm which uses $\lceil \log_3 n \rceil$ weighings, which is optimal by the argument outlined by Tom van der Zanden. Let's assume for simplicity that $n$ is a power of 3, leaving the general case as an exercise. Suppose we are given $3^k$ objects, which we divide into three groups $X,Y,Z$ of size $3^{k-1}$. We weight $X$ against $Y$. If $X > Y$, we recurse with $X$; if $Y > X$, we recurse with $Y$; if $X = Y$, we recurse with $Z$. After $k$ such steps, we will have zeroed in on a single object.

For the lower bound, suppose that we only do $k$ weighings. There are $3^k$ possible outcomes of this weighings – each one can be either "left side heavier", "right side heavier", or "both have the same weight" – and each of them causes the algorithm to output a definite answer. Since any of the $n$ objects could be the heavier one, we must have $3^k \geq n$. This argument will make more sense after you review the $\Omega(n\log n)$ comparison lower bound for sorting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.