[Solved]: is there a sorting algorithm of order $\log n!$

Problem Detail: 

Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are algorithms of order $n\log n$, but since $n!$ grows much slower than $n^n$, I wish to know of there is any algorithm of this order.

Asked By : sai

Answered By : David Richerby

By Stirling's approximation, $$\log(n!) = n\log n - n + O(\log n) = \Theta(n\log n)\,,$$ so, yes, there are lots of sorting algorithms that run in time $O(\log(n!))$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25959

3.2K people like this

 Download Related Notes/Documents