Limited binding for sorting compared

Question

Today I read Julien Walker's wonderful article on sorting - Eternally Confuzzled - The Art of Sorting , and one thing caught my attention. I do not quite understand the part where the author proves that for sorting by comparison we are limited by the lower boundary Ω (N · log N)

Lower scores are not so obvious. The smallest possible estimate for most sorting algorithms is Ω (N · log N). This is because most sorting algorithms use element comparisons to determine the relative order of elements. Any algorithm that sorts by comparison will have a minimum lower bound Ω (N · log N), because the comparison tree is used to select the sorted permutation. The comparison tree for the three numbers 1, 2 and 3 can be easily built:

1 < 2 1 < 3 1 < 3 2 < 3 3,1,2 2,1,3 2 < 3 1,2,3 1,3,2 2,3,1 3,2,1 

Notice how each element compares with every other element, and each path results in a real permutation of the three elements. The height of the tree determines the lower bound of the sorting algorithm. Since there must be so many leaves that there are correct permutations for the algorithm to be correct, the smallest possible height of the comparison tree is log N ! , which is equivalent to Ω (N · log N) .

This seems to be very reasonable to the last part (in bold), which I don't quite understand - like log N! equivalent to Ω (N · log N). I have to skip some of my CopmSci courses and cannot get the last transition. I look forward to this help, or for some reference to other evidence that we are limited to Ω (N · log N) if we use sorting by comparison.

Answer 1

You have not missed anything from the CompSci class. What you missed was a math class. The Wikipedia page for Stirling's approximation shows that log n! asymptotically n log n + lower order terms.

Answer 2

• N! <N ^ N
• ∴ log N! <log (N ^ N)
• ∴ log N! <N * log N

Moreover, you can prove θ (log N!) = O (N log N). The proof of the same for Ω remains as an exercise for the reader, or a question for the mathematician stackexchange or theoretical computer science stackexchange .

Answer 3

My favorite proof of this is very elementary.

N! = 1 * 2 * .. * N - 1 * N

We can make a very light lower bound, pretending that the first half of these works does not exist, and then that the second half is only N / 2.

(N / 2) ^ (N / 2) <= N!

(N / 2) ^ (N / 2) = N / 2 * log (N / 2) = N / 2 * (log (N) - 1) = O (n log n)

So, even when you take only the second half of the expression and pretend that all these factors are no more than N / 2, you are still in the O (n log n) region for the lower boundary, and this is super elementary. I could convince the middle school student of this. I can’t even get the Stirling formula.