I am a math student and I have been asked to help grade answer sheets for an Algorithms course as one of my professors is unwell. While I am quite familiar with combinatorial algorithms, I am not well versed in sorting/searching algorithms. One of the problems that has been asked is this one.

‘Construct an algorithm to find the log(log(n)) smallest elements from an array of size n with the goal of minimising time complexity’.

The output need not be sorted. One just needs to zero in on the smallest log(log(n)) elements. I have been told by the professor that I am to grade based on worst case time complexity.

Sorting the array can be done in nlog(n) at worst. I have seen another post (Algorithm to find k smallest numbers in array of n items) that addresses this problem but some of the answers seem to be concerned with average time complexity and not worse case time complexity. This same post gives a method that does it in nlog(k). Is this lowest one can go or is there an O(n) algorithm? I would like to know the algorithm that has the least worst case time complexity.