Suppose number is given x we need to find it appears maximum number of times or not i.e more than n/2 times or not.

Array is not give in sorted order So use Inoredr Traversal and sort it **O(n)**. Logic over here is find the index of **x** into the array by using Binary search **O(logn)** time suppose index is** i**. Now check element at **(i + n/2) =O(1)** also **x** if yes than it is maximal element else not.

If Array has given in sorted order than Time complexity will be **O(logn)** but Here **O(n). **

**Assuming BST available. If not available than O(nlogn) should be the ans **

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Same procedure apply for when x is not given .

Step1: Build BST= **O(nlogn)** = Sort the array + Than build BST = O( nlogn + n )

Step2. Each Element search into BST and check it's index **i **and** i+ (n/2)**^{th} element = O(**nlogn**)

So Time complexity =** O(nlogn)**

----------------------------------------------------------------------------------------------------------------------------------------------------------------

**Improvement Welcomes :**