What is the worst-case time complexity of the Heap sort?
2018
What is the worst-case time complexity of the Heap sort?
- A.
O(n)
- B.
O(n2)
- C.
O(n log n)
- D.
O(n3)
Attempted by 391 students.
Show answer & explanation
Correct answer: C
Heap sort has a worst-case time complexity of O(n log n). This occurs because building the heap takes O(n) and extracting elements takes O(log n) for each of the n elements.