CareerCup

I think O(logn) will be the answer b/c if no is present it will be at middle pos.Now we hv to count how many times it occurs in array (for that find first occurance and last occurance using binary search in O(logn) time ) if it is more than n/2 then this is the number.so time is O(1) + O(logn) ie O(logn)

I think the previous comments misunderstood the question. The question is to check if the sorted array contains a number that repeats at least n/2 times. The answer to this question is either yes or no (so the array might not contain such a number).

We know that if such a number exists than it will appear in the n/2-th position, so we can search for the first and last occurances of this number to determine if it appears more than n/2 times. This will take O(log n) time using binary search.

My thinking is log(N) works using a modified binary search. If the central element is not the majority element then we know there's no majority element. If it is, then choose the half-way point for both halves and check whether they are the majority element. If they both are, you're done. If not, then for the half that is not, set the 'upper' bound to the element you're currently at and look in the middle of where you're at and the center, and for the other half set the 'lower' bound and look in the middle. If you now have two majority elements you're done, else keep repeating the process. These two illustrations show what I mean:

x x x x x x x a (a) a a a a a a a x
x x x x >x x x a (a) a a a a< a a a x
x x x x x x >x a (a) a a a a a a< a x
x x x x x x x >a (a) a a a a a a a< x

[x x x x >x a a a] (a) [a a a a< a x x x]
x x x x [x a >a a] (a) a a a a [a x< x x]
x x x x [x >a] a a (a) a a a a [a< x] x x

You're doing 2 * log(N), so should be log(N) all up.

All the answers only prove an upper bound, i.e. require no more than O(log n).

The question is asking for a tight bound. For instance, why can't the answer be c? (iterated log I believe).

yes correct!!

If the number appears at middle then we can find the leftmost occurance(l) of element and rightmost occurance(r) in log*n time using Interpolation search .So,if r-l+1>=n/2 we can say it occurs more than n/r times

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is:
Theta(1)

This is because since the array is sorted then the number which is repeated more than n/2 times will appear as the middle element in array, that is, it will appear at index n/2 for (both even and odd n).

It would take constant time that is theta(1)

The fact it appears at index n/2 dose not tell us anything about of number of appearances of it.
However two comparisons:

x == a[n/4-1]
x == a[3*n/4+1]

will give the answer (and it's still O(1)).

theta(1) - only 3 comparisons required. If the value is present at n/2, n/4 and 3n/4 positions, we are sure that it is repeated more than n/2 times.

theta(1) will be the answer ,, since that number will definitely occupy (n/2)th position of array
so just compare with A[n/2].
In any possible permutation A[n/2] will always be one of these numbers.