clrs problems 4-5 chip testing

Chip A says	Chip B says	Conclusion
B is good	A is good	both are good, or both are bad
B is good	A is bad	at least one is bad
B is bad	A is good	at least one is bad
B is bad	A is bad	at least one is bad

Pair-wise comparison

• Pick any two chips and test them together
• If we have the first outcome then pick any of the two chips and throw it away. Put the other into the output set.
• If we have any of the other outcomes throw away both chips.
• Repeat this until we have at least two chips available
• If we are left with only one chip then add it to the output set if the number of tests with the first outcome is even and throw it away otherwise.

The recurrence for the problem is T(n) = T(n/2) + n/2