Question

How many elements can be sorted in O(logn) time using Heap sort?

(a) O(1)

(b) O(n/2)

(c) O(logn/log(logn))

(d) O(logn)

The question was asked during an interview for a job.

Question is from Heapsort in division Sorting of Data Structures & Algorithms II

Answer 1

Correct choice is (c) O(logn/log(logn))

The explanation is: The time complexity of Heap sort is O(klogk) for k input elements,

for k = logn/log(logn),

O(klogk) = O(logn/log(logn) * log(logn/log(logn)))

∴ O(klogk) = O(logn/log(logn) * (log(logn) – log(log(logn))))

= O(logn)

Hence the correct option is O(logn/log(logn)).