5. (20 pts) You are given n numbers a1, a2,....an. It takes constant time to check...

Transcribed Image Text:

5. (20 pts) You are given n numbers a1, a2,....an. It takes constant time to check whether two numbers a; and a; are of the same value. The goal is to check whether more than half of the numbers have the same value. Please state the steps of your algorithm clearly, prove that it is correct, and analyze its running time. (1) (10 pts) Design an O(n log n) time algorithm to solve the problem. (2) (10 pts) Design an O(n) time algorithm to solve the problem. (Hint: Show that using linear time, the problem size can be reduced by at least half.) 5. (20 pts) You are given n numbers a1, a2,....an. It takes constant time to check whether two numbers a; and a; are of the same value. The goal is to check whether more than half of the numbers have the same value. Please state the steps of your algorithm clearly, prove that it is correct, and analyze its running time. (1) (10 pts) Design an O(n log n) time algorithm to solve the problem. (2) (10 pts) Design an O(n) time algorithm to solve the problem. (Hint: Show that using linear time, the problem size can be reduced by at least half.)