When the size of your problem reduced to 2, it’s the base case of your

recursion, it’s false that we pair up two remaining elements. so it’s

sufficiently, first count number of occurrence of two remaining

elements in $A$.for your problem we act as follow:

we check the whole array to count number of occurrence $A(i)=3$, and

number of occurrence of $A(i)=1$ and then if number of occurrence

$3geq frac{n}{2}+1$ or if number of occurrence $1geq frac{n}{2}+1$, we print it.

but the main problem is we must prove the correctness and running time of algorithm.

Suppose $mathcal{X}$ is majority element, because of, $mathcal{X}$ is majority element, then the number of occurrence of it, is grater than

$frac{n}{2}$, so after pair up, at least there is one pair that elements are $mathcal{X}$, otherwise it contradict with this fact that $mathcal{X}$ is majority element.

On the other hand, at most all elements of array $A$ be $mathcal{X}$, so both elements of a pair be equal, as a result at most half of the elements remain in each recursion.

Therefore one of the at most $frac{n}{2}$ elements be $mathcal{X}$. And we do our divide an conquer the problem until remain only two element.

Our statement holds only if $A$ contains $mathcal{X}$. So after we get base that $n=2$, it’s sufficient to for each of two remaining elements we check number of occurrence it.

Suppose the remaining elements is a,b:

```
A,B=0
for i = 1 to n
if (a==A(i))
A++
if (b==A(i))
B++
if(a> n/2)
print a
else if (b> n/2)
print b
else
print "there is no majority in the array"
```

Because at each iteration at most half of the elements are remain

$$T(n)=T(frac{n}{2})+O(n)$$

$$=O(n)$$

**Note that at each iteration pairing up of $n$ elements need $O(n)$ time.**