Topic: Algorithms
Worst case time complexity of heap sort for n elements
- A. O(nlogn)
- B. O(logn)
- C. $O(n^{2})$
- D. $O(n)$
Answer: A. O(nlogn)
Explanation: Building the heap takes $O(n)$ time. Extracting the maximum element and heapifying takes $O(\log n)$ time, which is done $n$ times. Thus, the worst-case time complexity of heap sort is $O(n \log n)$.