title: Time complexity
body: <p>The Problem is finding majority elements in an array.
  I understand how this algorithm works, but i don't know why this has O(nlogn) as a time complexity.....</p>
  
  <hr>
  
  <p>a. Both return \no majority." Then neither half of the array has a majority
  element, and the combined array cannot have a majority element. Therefore,
  the call returns \no majority."</p>
  
  <p>b. The right side is a majority, and the left isn't. The only possible majority for
  this level is with the value that formed a majority on the right half, therefore,
  just compare every element in the combined array and count the number of
  elements that are equal to this value. If it is a majority element then return
  that element, else return \no majority."</p>
  
  <p>c. Same as above, but with the left returning a majority, and the right returning
  \no majority."</p>
  
  <p>d. Both sub-calls return a majority element. Count the number of elements equal
  to both of the candidates for majority element. If either is a majority element
  in the combined array, then return it. Otherwise, return \no majority."
  The top level simply returns either a majority element or that no majority element
  exists in the same way.</p>
  
  <p>Therefore, T(1) = 0 and T(n) = 2T(n/2) + 2n = O(nlogn)</p>
  
  <hr>
  
  <p>I think,</p>
  
  <p>Every recursion it compares the majority element to whole array which takes 2n.</p>
  
  <pre><code>T(n) = 2T(n/2) + 2n = 2(2T(n/4) + 2n) + 
        2n = ..... = 2^kT(n/2^k) + 2n + 4n + 8n........ 2^kn = O(n^2)
  </code></pre>