Find top log(n) or top sqt(n) values in an array of integers

Question

Do you understand what this question means

Find top log(n) or top sqt(n) values in an array of integers in less than linear time.

If you don't, here is the question http://www.careercup.com/question?id=9337669.

Could you please help me in understanding this question and then may be get it solved. (Although once i understand i might get it solved too)

Thanks for your time.

Answer 1

Assuming the array is not sorted, This problem is Omega(n), since you need to read all elements [finding max is Omega(n) problem in non-sorted array, and this problem is not easier then finding max]. So, there is no sublinear solution for it.

There is O(n) [linear] solution, using selection algorithm

1. find the log(n) biggest element. //or sqrt(n) biggest element...
2. scan the array and return all elements bigger/equal it.

(*)This pseudo code is not correct if the array contain dupes, but trimming the dupes in a second step is fairly easy.

Answer 2

For non sorted array the complexity is linear, but it can be possible to improve the performance by observing that log(n) and sqrt(n) are both monotonic growing function, hence max(log(n),...) is also log(max(n,...)) and same for sqrt.

So just find max(n) (linearly) and calculate log and sqrt.