I think the answer should be O(1) as the middle element can be found in constant time as the n/2th element is the middle element in. Once found, it can be compared. If it is found to be 1 then the majority is 1 otherwise 0 as it is given as sorted array.