GATE CS 2008 Q40 — Asymptotic Worst Case Time and Space Complexity

To determine if any integer appears more than $\frac{n}{2}$ times in a sorted array $A$ of size $n$, we can use the following approach:

1. Identify the Candidate: If an element appears more than $\frac{n}{2}$ times in a sorted array, it must occupy the middle position of the array. Let this candidate element be $x = A[\lfloor n/2 \rfloor]$.
2. Find the Boundaries: To check if $x$ actually appears more than $\frac{n}{2}$ times, we need to find its first occurrence (index $L$) and its last occurrence (index $R$) in the array.
3. Binary Search: Since the array is sorted, we can find both $L$ and $R$ using binary search. Each binary search takes $\Theta(\log n)$ comparisons.
4. Verify the Count: If $(R - L + 1) > \frac{n}{2}$, then $x$ is the majority element. Otherwise, no such element exists.

Since binary search is optimal for searching in a sorted array, the minimum number of comparisons required in the worst case is $\Theta(\log n)$.