# Chip testing problem

An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the engineer cannot trust the answer of a bad chip. Assume that thenumber of good chips is greater than the number of bad chips. Thenanswer the following question:

Is it possible to design an algorithm that finds all the good chips after at most O(n log n) pairwise tests?

• Is it possible to design an answer to the question of whether this is a school assignment? – Mark L. Stone May 30 at 20:50
• I know two solutions one in O (n ^ 2) and one in O (n) but I would like to know if a solution is possible in O (n log n). – neider May 30 at 21:22
• Hmm, isn't O(n) better than O(n logn), leaving constants aside? – Mark L. Stone May 30 at 22:15
• @MarkL.Stone is correct. $O(n)$ is better. Even more, if we look at $O$ notation (and not $\Theta$ - tight notation), $O(n)$ would qualify for an $O(n\log n)$. – Anton Menshov May 30 at 22:36