the answer to 3 is theta(1).
this is because the array is already sorted. if at all an element occurs more than n/2 times it has to be present as the middle element also i.e starting from the first position to the middle element or middle element to last position .so we only need to check the first/last element with the middle element. if at all one of them matches then we can be sure that the first/last element occurs more than n/2 times.no other element can occur more than n/2 times.
EDIT:
sorry the above analysis is wrong. we can have an array like this also
1 2 2 2 2 2 3
1!= middle element and 3 != middle element but still we have an integer with its occurrence > n/2
:(
well i guess the only thing that can be done is to have a frequency table and calculate the frequencies of all elements in theta(n).
then find the the frequency > n/2 in O(n).
therefore O(n) should be the answer i guess.