Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A question about recursive algorithm design.

Let A be a set of n items. The only operation available to you is "compare(x,y)", which returns "ture" if x = y and "false" otherwise. An item is said to be a majority item if it occurs at least n/2 + 1 times. Write an O(n) worst-case time (recursive) algorithm that decides if a majority item exists, and if so, identifies it. Explain why it takes O(n) time.

share|improve this question
2  
This seems like homework. Did you try solving it? Where did you get stuck? –  Yuval Filmus Jan 15 '12 at 20:58

1 Answer 1

It is pretty easy. First we need to find a candidate. Divide the items into 2 groups $a$ and $b$, if $a_1$and $b_1$ are two elements and $a_1$ != $b_1$, then remove both of them, then remove one group of the rest; majority still remains and we reduce it by at least a half. This is the recursion. Use $N-1$ comparisons to check if candidate really is a majority. To explain the time complexity, you might need master theorem. It is $O(n)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.