edited by
3,348 views
0 votes
0 votes

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

  1. Θ(n)

  2. Θ(logn)

  3. Θ(log∗n)

  4. Θ(1)

isnt O(1) enough for this.....the answer give in this site is log N

can i get a counter on why O(1) wont work ?

edited by

1 Answer

0 votes
0 votes
The ques says to find  no. of comp inorder to find a number(Say 'K') in sorted array more than n/2 times.

Now Just saying that check with the middle element won't work as Eg:-

1,1,2,3,3 Here middle element is 2 but kits not more than n/2 times , therefore O(1) is not possible acc. to me,

Now with Binary Search Once You can find the first index of that Number K in logn time, and in another logn time of binary search to find the last index, now checkthe difference of the two positions to be more than n/2 ,  Hence overall O(logn) comparisons needed.

Related questions

8 votes
8 votes
2 answers
2
1 votes
1 votes
0 answers
3
3 votes
3 votes
1 answer
4
Sanjay Sharma asked Feb 20, 2018
1,040 views
An array A is of length n has log( n) distinct numbers.What is the time complexity of sorting A by best comparison based algorithm ?