The average complexity of a coin-weighing problem
Given a set of n coins, some of them weighing H, the others weighing h, h < H, we prove that to determine the set of heavy coins, an optimal algorithm requires an average of 1+rho(2)/1+rho+rho(2) n + O(1) comparisons, using a beam balance, where rho denotes the ratio of the probabilities of being light and heavy. A simple quasi-optimal algorithm is described. Similar results are derived for the majority problem. (C) 1996 John Wiley & Sons, Inc.
average complexity quasi-optimal algorithm graph connected component martingale