You have n widgets, each of which is of a certain type. You want to determine whether there is a majority type; i.e., if there is a type t such that the number of widgets of type t is greater than n/2. For instance, the set of 7 widgets with types A, A, B,C, A, C, A, respectively has a majority type A since there are 4 widgets of that type. On the other hand, the set of 6 widgets with types A, A, B, C, D, A has no majority type. Unfortunately, you are unable to determine the type of any given widget. Instead, the only operation available to you is to call a subroutine Equality Test that takes two widgets as input and returns True if both are of the same type and False otherwise. Give a divide-and-conquer algorithm for determining if there is a majority type in a given set of n widgets. The running time of your algorithm is the number of calls made by your algorithm to Equality Test. Analyze the running time of your algorithm. Ideally, the running time of your algorithm should be O(nlogn). You will receive extra credit if the running time of your algorithm is O(n).
You have n widgets, each of which is of a certain type. You want to determine whether there is a majority type; i.e., if there is a type t such that the number of widgets of type t is greater than n/2. For instance, the set of 7 widgets with types A, A, B,C, A, C, A, respectively has a majority type A since there are 4 widgets of that type. On the other hand, the set of 6 widgets with types A, A, B, C, D, A has no majority type. Unfortunately, you are unable to determine the type of any given widget. Instead, the only operation available to you is to call a subroutine Equality Test that takes two widgets as input and returns True if both are of the same type and False otherwise. Give a divide-and-conquer
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
