More formally, you are given an array X[1..n]. The only method you have to compa

Question

More formally, you are given an array X[1..n]. The only method you have to compare elements of X is a procedure Same(x, y) that returns True if elements x and y are equivalent and False otherwise. Design and analyze an algorithm to output a member of X whose equivalence class contains strictly greater than n/2 members. For your analysis, give an asymptotic bound on the number of times your algorithm calls Same. Note: Expressing the number of calls to Same as a recurrence is worth substantial partial credit, but you should be able to give an asymptotically tight answer by now.

Explanation / Answer

One of the approach can be as follows:
We will consider the element of X one by one. For every element we will call the Same() function with this member and all the other members of X. While doing this as soon as we get a member whose equivalence class has members more than n/2 we can stop the processing.The complexity of this approach will be O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.