1) Among n identical-looking coins, one is fake. The fake coin is known to be lighter than the genuine one. With a balance scale, we can compare any two sets of coins. Design an efficient (with minimum number of weighing) divide-into-3 algorithm for detecting the fake coin. Set up a recurrence relation for the number of comparisons or weighing for this algorithm and solve it by backward substitution method for n = 3^k

²⁾ Let C(n) denote the number of comparisons performed by quicksort in sorting an array of size n in the worst case. Write the recurrence relation for C(n) and solve.