Big O Notation of the terms f(n) = n*log(n!) and g(n) = 3n*(log n)^(5n)

Question

I have:

• 𝑓(𝑛) = 𝑛 * log(𝑛!)
• 𝑔(𝑛) = 3𝑛 * log(n)⁵ⁿ

I must show whether:

• 𝑓(𝑛) = Ω(𝑔(𝑛)) or/and
• 𝑓(𝑛) = O(𝑔(𝑛))

At first I tried to simplify 𝑔(𝑛). This brings me to: 𝑔(𝑛) = 15𝑛² * log(n)

My next step would be to guess the factorial in 𝑓(𝑛). For this I estimate an upper bound of 𝑛^𝑛. So now I can compare the two terms.

I know that: 𝑓(𝑛) ≤ O(𝑔(𝑛))

𝑛 * log(𝑛)^𝑛 ≤ c * 𝑛² * log(n)
𝑛² * log(n) ≤ c * 𝑛² * log(n)

So for c ≥ 1 → 𝑓(𝑛) = O(𝑔(𝑛))

But how do I prove this for Ω? Or is my approach for O even right?

Answer 1

To compare these functions you just need to take a log from them and note that log(n!) is in Theta(n log(n)). Hence, we have the following:

log(f(n)) = log(n log(n!)) = log(n) + log(log(n!)) => log(f(n)) is in `Theta(log(n))`

log(g(n)) = log(3n) + log(log(n)^(5n) = log(3n) + 5n log(log(n)) => log(g(n)) is in `Theta(n log(log(n)))`.

Therefore, as log(n), f(n), and g(n) are an increasing function, we can say that f(n) is in o(g(n)) (little-oh). Consequently, f(n) cannot be in Omega(g(n)), and definitely f(n) is in O(g(n)) (because Big-O(g(n)) is a subset of little-o(g(n))).

Answer 2

You will need Sterling's approximation. In short it states that ln(n!) = n * ln(n) - n + Θ(ln(n)) which directly leads to Θ(n * ln(n)) = Θ(ln(n!) See also this answer.