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