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.


2 Answers 2


$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.

  • 1
    $\begingroup$ It makes sense, thank you very much! $\endgroup$ Apr 7, 2020 at 21:07

$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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.