0
$\begingroup$

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.

  • 2
    This seems like homework. Did you try solving it? Where did you get stuck?2012-01-15

1 Answers 1

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)$.