Question: describe a divide and conquer algorithm The problem to solve is to find the heaviest ball and lightest ball within n balls. Assume that no
describe a divide and conquer algorithm
The problem to solve is to find the heaviest ball and lightest ball within n balls. Assume that no 2 balls have the same weight and all balls look the same. The only tool you have is a balance scale, which can tell between 2 balls who is heavier and who is lighter. The brute force way is to weigh every ball comparing it with the current heaviest ball and current lightest ball, replace the current heaviest and current lightest if necessary, which requires 2(n-1) times usage of the balance scale. Please describe a divide and conquer algorithm to solve the same problem with fewer number of balance scale usage and estimate how many times it should be used in your algorithm (number of comparisons, not big oh).
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
