You have 210 coins that are all supposed to be gold coins of the same weight, but you know that one coin is fake and weighs less than the other coins. You have a balance scale: you can put any number of coins on each side of the scale at one time and it will tell you if the two sides weigh the same, or which side is lighter if they do not weigh the same. Write an algorithm to find the fake coin What is the worst, average, and best running times of the algorithm for an input size 2n

Please specify the average running time as well, not just the worst and best.