Multiple choice

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

  1. $\Theta(1)$
  2. $\Theta(\sqrt{\log} n)$
  3. $\Theta(\frac{\log n}{\log \log n})$
  4. $\Theta(\log n)$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

After constructing a max-heap in the heap sort, the time to extract maximum element and then heapifying the heap takes $\Theta$(log n) time by which we could say that $\Theta$ (log n) time is required to correctly place an element in sorted array. If $\Theta$ (logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is $\Theta$ (1).

Keep practicing — related questions