1 votes 1 votes What is the Best Case run time of Heap Sort ? A. $O(1)$ B. $O(n)$ C. $O(n \log n)$ D. $O(\log n)$ Algorithms algorithms sorting binary-heap heap-sort + – Himanshu1 asked Jan 20, 2016 retagged Jan 20, 2016 by Himanshu1 Himanshu1 1.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 6 votes 6 votes option C. Best, average and worst case time complexity of heap sort is $O(n \log n)$. Arjun answered Jan 20, 2016 selected Jan 20, 2016 by Pooja Palod Arjun comment Share Follow See all 3 Comments See all 3 3 Comments reply anoop commented Jan 20, 2016 reply Follow Share Theta notation is ideal since all cases are same. 1 votes 1 votes Arjun commented Jan 20, 2016 reply Follow Share Nopes. Simply because all cases are same does not allow us to replace $O$ with $\Theta$. Because all the cases might have a lower bound also. But we know that for any comparison based sorting, time complexity is $\Omega(n \log n)$. Using this we can replace $O$ with $\Theta$. 2 votes 2 votes neel19 commented Sep 28, 2021 reply Follow Share Sir, if all the elements are the same then TC is O(n). 0 votes 0 votes Please log in or register to add a comment.