Why is the time complexity of Heapsort O(n logn) and not O(log(n!))?

Viewed 171

Heapsort, every time it iterates within, the heapsize reduces by one, and hence should have a time complexity of Sigma(i=N to 1) O(log i) which would result in O(log n!). And why can't we just report the time complexity of Heapsort as O(log n!).

I came across Stirling's Approximation while trying to answer this question, and realised that log n! -> n logn as n -> inf. Also, is the reason why we agree upon O(n logn) instead of O(log n!), even though log(n!) is smaller than n logn for a wide range of values?

0 Answers
Related