Complexity of finding a majority element 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??
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), &amp; \text{if } n &gt; 2, \\
O(1), &amp; \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 &gt; \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), &amp; \text{if } n = 0, \\
T(n-1) + O(n), &amp; \text{if $n$ is odd}, \\
T(n/2) + O(n), &amp; \text{if $n$ is even},
\end{cases}
$$
whose solution is $T(n) = O(n)$.