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 :