Question

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

(A) Θ (1)

(B) Θ (√log n)

(C) (log n / log log n)

(D) Θ(log n)

Answer 1

Correct option is (A) Θ (1)

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