Suppose you are given n number of coins, in that one coin is faulty, its weight is less than standard coin weight. To find the faulty coin in a list using proper searching method. What will be the complexity of searching method.

1. Name the coins as 1, 2, 3, 4 …..N.
2. We know that one coin is faulty as its weight is less than the standard coin weight.
3. Considering best outcome of balance, we can group the coins in two different ways, [(1, 2), (3, 4), ((N-1), N)] or [(1,…..((N/2)-1) and ((N/2),……N))].
4. Consider the first group, pairs (1, 2) and (3, 4). We can check (1, 2), if they are equal we go ahead with (3, 4) and so on.
5. We need N/2 weighing in worst case.
6. With the second group, weigh [(1,…..((N/2)-1) and ((N/2),……N))]. Pick up the lighter pair, and we need N/2 weighing to find odd one.
7. Both the combinations need N/2 weighing in case of N coins with prior information of one coin is lighter.

Analysis:

1. In general, if we know that the coin is heavy or light, we can trace the coin in log_3⁡N trials (rounded to next integer). If we represent the outcome of balance as ternary tree, every leaf represent an outcome.
2. Since any coin among N coins can be defective, we need to get a 3-ary tree having minimum of N leaves. A 3-ary tree at k-th level will have 3^k leaves and hence we need $3^k \gt= N$.
3. In other words, in k trials we can examine up to 3^kcoins, if we know whether the defective coin is heavier or lighter.
4. Given that a coin is lighter, verify that 3 trials are sufficient to find the odd coin among 12 coins, because $3^2 \lt 12 \lt 3^3$.