Less work

Computer Science Level 2

Give a sorted array of $n$ elements, what is the minimum number of comparisons needed to check whether a certain element occurs more than half of the time?

Details and Assumptions

-No auxiliary data structure is allowed.

O(1)

O(\log(n))

O(n\log(n))

O(n)

2 solutions

Canwen Jiao
Jul 22, 2018

We do a binary search on the array. Since the array is sorted, if an element appears for more than half of the time, the middle array will necessarily be that element, which means if the middle element is not the element, then it can't appear more than half of the time. If it is, then we need to find the first and last appearances of that element, which will take $O(log(n))$ time respectively, and then subtract the indexes to compare to $\frac{n}{2}$ .

Owen Leong
Oct 31, 2015

$O(n\log(n))$ to find the first occurrence, $O(n\log(n))$ to find the last occurrence, $O(1)$ to find the number of occurrences and compare with the number of elements. Put them altogether and you get $O(2n\log(n)+1) = O(n\log(n))$

This is incorrect, it should be O(log n) each for finding the first instance and the last instance (not O(n log n) as posted.) The rest of the reasoning is correct.

Dominique Danco - 3 years, 9 months ago

Less work

2 solutions

1 pending report

Vote up reports you agree with