Algorithms

You are given n metal balls B_1,.......,B_n, each having a different weight. You can compare the weights of any two balls by comparing their weights using a alance to find which one is heavier.

Consider the followin algorithm to find the heaviest ball:

i. Divide the n balls into n/2 pairs of balls

ii. Compare each ball with its pair, and retain the heavier of the two

iii. repeat this process until just one ball remains.

Question: Show that for "n" balls, the algorithm uses at most n comparisons.

(Please illustrate detailed understanding of the problem)

Thank you!