Complexity of finding a majority element

Question

I was given a question that is stated that;

Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they’ve confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to the same account. It’s very difficult to read the account number of a bank card directly, but the bank has 1 a high-tech ‘equivalence tester’ that takes two bank cards and, after performing some computations, determines whether they are equivalent. Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them into the equivalence tester. Show how to decide the answer to their question with only O(nlog n) invocations of the equivalence tester.

I proposed an algo for this problem that is like this;

For the equivalent majority there must be majority of the equivalent cards on one side of the n cards if we divide them into two halves. So one of the two sides must return one card that has majority more than n/2 in whole list.

Let’s say equivalentTest​ is the function that takes two bank cards and, after performing some computations, determines whether they are equivalent.

Function checkMajority(c, M)
    i = count = 0
    While i less than length of M:
        if (M[i] is not actual c) and (equivalentTest(M[i], c) == true) then:
            count ++
        Endif
    Endwhil
    If count is greater than half the length of M then:
        Return true
    Else
        Return false
    Endif


Function divide_and_find(M)
    If M.length = 1
        Return M[0]
    Else if M.length = 2
        If equivalentTest(M[0], M[1]) == true
            Return M[0] or M[1]
    Divide M
    M1 = assign first half
    M2 = assign second half
    c = divide_and_find(M1)
    if c is returned then
        found = checkMajority(c, M)
        If found = true then
            Return c
        Else
            c = divide_and_find(M2)
            found = checkMajority(c, M)
            If found = true then
                Return c
            Else
                Return ‘not found’
            Endif
        Endif
    Endif
    Return ‘not found’

According to my understanding,

The algorithm complexity is O(nlogn) because we have used divide and conquer strategy. There would be (logn) steps and each step would take O(n) time for checking the majority. So the complexity would be O(nlogn)

But at the same time, I think it will take O(n*n).. that is big O of n square, In worst case scenario. Because then it will check n cards for n cards, to find duplicate cards.

Can any one help me out in resolving my confusion??

Answer 1

Let us denote the running time of your algorithm on arrays of size $n$ by $T(n)$. Then $$ T(n) = \begin{cases} T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n), & \text{if } n > 2, \\ O(1), & \text{if } n \leq 2. \end{cases} $$ The master theorem now shows that $T(n) = O(n\log n)$.

---

Here is an $O(n)$ algorithm:

find-majority-element(A):
  n = len(A)
  if n = 0:
    return "none"
  if n is odd:
    y = last element of A
    if y is a majority element:
      return y
    A' = A with last element removed
    x = find-majority-element(A')
    if x is a majority element:
      return x
    otherwise:
      return "none"
  partition A into m = n/2 pairs (a_1,b_1),...,(a_m,b_m)
  construct an array B consisting of all a_i such that a_i = b_i
  x = find-majority-element(B)
  if x is a majority element:
    return x
  otherwise:
    return "none"

Clearly if there is no majority element, the algorithm returns "none". Now suppose that $x$ is a majority element. We will show that the algorithm returns $x$. We will do this by proving the following claim by induction on $n=\mathrm{len}(A)$:

If $A$ contains a majority element $x$, then find-majority-element($A$) returns $x$.

Suppose first that $n=2m+1$ is odd, so that $x$ appears at least $m+1$ times. If $x$ is the last element, then find-majority-element($A$) will return it. Otherwise, $x$ is a majority element of $A'$ as well, and so find-majority-element($A'$) will return $x$, causing find-majority-element($A$) to return it as well.

We can now assume that $n = 2m$ is even. Suppose that $B$ contains $k$ many $x$'s and $\ell$ many other elements. We can upper-bound the number of copies of $x$ in $A$ by $2k + (n-2k-2\ell)/2 = m + k - \ell$. On the other hand, the number of copies is at least $m+1$, and so $k > \ell$. In other words, $x$ is a majority element in $B$ as well. Therefore find-majority-element($B$) will return $x$, causing `find-majority-element($A$) to return it as well.

Denoting by $T(n)$ the maximum running time of the procedure on arrays of length at most $n$, we get the recurrence $$ T(n) \leq \begin{cases} O(1), & \text{if } n = 0, \\ T(n-1) + O(n), & \text{if $n$ is odd}, \\ T(n/2) + O(n), & \text{if $n$ is even}, \end{cases} $$ whose solution is $T(n) = O(n)$.