Lowed bound for sorting by comparison

Question

Today I was reading a great article from Julienne Walker about sorting - Eternally Confuzzled - The Art of Sorting and one thing caught my eye. I don't quite understand the part where the author proves that for sorting by comparison we are limited by Ω(N·log N) lower bound

Lower bounds aren't as obvious. The lowest possible bound for most sorting algorithms is Ω(N·log N). This is because most sorting algorithms use item comparisons to determine the relative order of items. Any algorithm that sorts by comparison will have a minimum lower bound of Ω(N·log N) because a comparison tree is used to select a permutation that's sorted. A comparison tree for the three numbers 1, 2, and 3 can be easily constructed:

                         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 every item is compared with every other item, and that each path results in a valid permutation of the three items. The height of the tree determines the lower bound of the sorting algorithm. Because there must be as many leaves as there are 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).

It seems to be a very reasonable until the last part (bolded) which I don't quite understand - how log N! is equivalent to Ω(N·log N). I must be miss something from my CopmSci courses and can't get the last transition. I'm looking forward for help with this or for some link to other evidence that we are limited Ω(N·log N) if we use sorting by comparison.

Answer 1

You didn't miss anything from CompSci class. What you missed was math class. The Wikipedia page for Stirling's Approximation shows that log n! is asymptotically n log n + lower order terms.

Answer 2

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

With this, you can prove θ(log N!) = O(N log N). Proving the same for Ω is left as an exercise for the reader, or a question for mathematics stackexchange or theoretical computer science stackexchange.

Answer 3

My favorite proof of this is very elementary.

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

We can can a very easy lower bound by pretending the first half of those products don't exist, and then that the second half are all just N/2.

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

log((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 those factors are no bigger than N/2, you are still in O(n log n) territory for a lower bound, and this is super elementary. I could convince an average high school student of this. I can't even derive Stirling's formula by myself.