Question on sorting

The number of elements that can be sorted in Θ (log n) time using heap sort is

(A) Θ (1)
(B) Θ ( sq_root(log n) )
(C) Θ (log n/(log log n))
(C) Θ (log n)

Answer: C.

Explanation :

Sorting complexity of heap sort is O(n logn).

Lets assume that x number of elements can be sorted in log n time.
i.e., O(x log x) = O(log n)

Substitution method
Option A : x = O(1)

Complexity to sort the array of O(1) elements using heap sort is O(1 log(1)) = O(1). This is not an answer as O(log n) != O(1).

Option B : x = O (sq_root(log n))
Complexity to sort the array of O (sq_root(log n)) elements using heap sort is sq_root(log n)) log (sq_root(log n))) = O( sq_root(log n)) * log (log n) ) != O(log n)

Option C : x = Θ (log n/(log log n))
Complexity to sort the array of Θ (log n/(log log n)) elements using heap sort is
     =  O ( log n/(log log n) log (log n/(log log n)) )
     =  O ( log n/(log log n)  * [ log (log n) -  log (log log n)]
     =  O ( log n - [logn * log (log log n)/log log n)] )
     =   O (log n).

Option D : x = Θ (log n)
Complexity to sort the array of Θ (log n) elements using heap sort is
      = O (log n * log (log n)) != O(log n)
   
It is clear that C is the answer.

Topics to revisit :
Time complexity
Sorting
Heap sort

References :