The proof for the complexity of sorting algorithms

Question

The theorem denotes that:

Any comparison sorting algorithm performs Ω(nlg(n)) comparisons in the worst case.

To prove that I found:

Looking the worst case number of comparisons that an algorithm performs, means the longest path from the root to a leaf in its decision-tree.

As a binary tree of height h has at most 2^h leafs, and there are n! permutations (output), we have:

2^h ≥ n!

I understand that we can rewrite 2^h ≥ n! as h ≥ log2(n!) but how can we end up with:

h ≥ log2(n!) = Ω(n*lg(n)) ?

Answer 1

Applying Stirling's approximation to the log₂(n!) term gives:

n log₂(n) - log₂(e)*n + O(log₂(n))

which is Ω(n log₂(n))

Answer 2

n! is the product of n numbers that are less than or equal to n, so:

log(n!) < log(n^n)
=> log(n!) < n*log(n)

and n! is the product of n/2 numbers that are at least n/2, as well as some other numbers > 1, so:

log(n!) > log((n/2)^(n/2))  
=> log(n!) > n*log(n/2)/2
=> log(n!) > n*(log(n)-log(2))/2
=> log(n!) > n*log(n)/4 when log(n) - log(2) > log(n)/2
=> log(n!) > n*log(n)/4 when log(n) > 2log(2)
=> log(n!) > n*log(n)/4 when n > 4