Analysis of decision tree in sorting algorithms

Question

In a decision tree of height h in a sorting algorithm with n elements:

We have something like this:

n! <= 2^h

Hence h>=log(n!)

I know that n^n is greater than n!, but here we are talking about the lower bound of worst case scenario,the graph of log(n!) is lower than the graph of(log n^n). So simply the answer should be Ω(log n!) as it can't go any lower than that.

So how can we say after here that h= Ω(nlogn)..?

Answer 1

You're right that n! and nⁿ have different growth rates, but their logs (log n! and log nⁿ) actually have the same growth rate. @Salvador Dali has pointed out that Stirling's approximation is a great way to see this, but here's a different way to look at this.

First, note that log nⁿ = n log n via properties of logarithms. That's the easy one.

What about (log n!)? First, notice that

log n!

= log (n · (n-1) · (n-2) · .. · 2 · 1)

= log n + log (n-1) + log (n-2) + ... + log 2 + log 1

This again uses properties of logarithms. From this, we can see that log n! = O(n log n), since

log n + log (n-1) + log (n-2) + ... + log 2 + log 1

≤ log n + log n + log n + ... + log n + log n (n times)

= n log n

I'm also going to claim that log n! = Ω(n log n). Here's one way to see this. Look at the first n/2 terms of the above summation, which is

log n + log (n-1) + log(n-2) + ... + log(n/2)

Notice that this quantity is no smaller than

log (n/2) + log (n/2) + log(n/2) + ... + log(n/2) (n/2 times)

= (n/2) log (n/2)

That last quantity is Ω(n log n), so overall we see that log n! = O(n log n) and that log n! = Ω(n log n), so n! = Θ(n log n). In other words, log n! grows asymptotically at the same rate as log nⁿ, even though the original functions n! and nⁿ have different growth rates.

Hope this helps!

Answer 2

Basically here is an approximation for your log(n!):

You can prove it from Stirling's approximation, which is an approximation of a n!:

There they also give you a slightly less tight approximation:

If you are interested of how to prove it, just carefully use the log over the Stirling's formula.