You are given n metal balls B1, . . . , Bn, each having a different weight. You can compare the weights of any two balls by weighing them on a balance and finding which one is heavier.

(A) Consider the algorithm to find the heaviest ball as follows: 1. Divide the n balls into n 2 pairs of balls. 2. Compare each ball with its pair, and retain the heavier of the two. 3. Repeat the process, until just one ball remains. 1 Illustrate the weighings that the algorithm will do for data given n = 8 and the weights are B1 : 3, B2 : 5, B3 : 1, B4 : 2, B5 : 4, B6 : 0.5, B7 : 2.5, B8 : 4.5 .

(B) Show that for n balls, the algorithm in (A) uses at most n weighings.

(C) Describe an algorithm that uses the results of (A) to find the second heaviest ball using at most log2 (n) additional weighings. (

D) Illustrate the additional weighings that your algorithm in (C) will perform for the data from part (A).