1.

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»

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)).


Discussion

No Comment Found

Related InterviewSolutions