Complexity of $O(\log(n^n))$ vs $O(\log(n!))$

Question

Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?

And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$?

I'm just starting with this topic and not really sure if I'm getting it right.

Thanks and stay safe.

Answer 1

$O(\log n^n)$ and $O(\log n!)$ both describe the same set of functions.

Notice that $( \frac{n}{e} )^n \le n! \le n^n$ and hence:

$O(n \log n) = O(n \log \frac{n}{e}) = O( \log ( \frac{n}{e} )^n) \subseteq O(\log n!) \subseteq O(\log n^n) = O(n \log n)$.

This shows that all the above sets coincide.

Answer 2

$n^n$ is a lot larger than n!. The first multiplies n x x n x n x ... x n (n times), the latter multiplies 1 x 2 x 3 x 4 x ... x n. So it is obvious that $O(\log(n^n)) < O(\log(n!))$ is not true. $O(\log(n^n)) > O(\log(n!))$ is less obvious, but also not true.

That's because we are taking the logarithm on both sides. Taking logarithms changes products to sums and exponents to products (very roughly). And if we take the product for n!, it's obvious that we have n/2 factors greater than n/2, so n! > $(n/2)^{n/2}$. Taking the logarithm, log n! > (n/2) log (n/2). For n > 4 we have n/2 > $n^{1/2}$, therefore log n/2 > (log n) / 2, therefore log n! > (n/2) log (n/2) > n/4 log n = 1/4 log $n^n$.

So log n! = $\Theta(\log n^n)$.