Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term.

What is the best known lower bound for large $n$?

I couldn't even find $\lceil \log_2(n!)\rceil+1$ proved anywhere, but I suspect even $\lceil \log_2(n!)\rceil+\omega(1)$ might be known.
Some useful links: OEIS A036604 of known exact values, Wikipedia page, and Knuth: TAOCP Vol. 3 section 5.3.

  • 4
    $\begingroup$ It appears the error term can be reduced to $o(n)$, see cstheory.stackexchange.com/questions/41493/… $\endgroup$ Feb 1 at 11:41
  • $\begingroup$ I didn't realize this was an open problem, nice! $\endgroup$ Feb 1 at 15:15
  • $\begingroup$ Are you asking about worst-case or average-case? $\endgroup$ Feb 1 at 15:25
  • 1
    $\begingroup$ Worst case is enough for me. $\endgroup$
    – domotorp
    Feb 1 at 21:48
  • $\begingroup$ @domotorp Please @ me so I receive the notification. Also, just to emphasize it, we have equality for $n=21$, so a lower bound of $\lceil \log_2(n!)\rceil + 1$ can only hold for $n > 21$. $\endgroup$ Feb 2 at 13:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.