2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It makes sense, thank you very much! $\endgroup$ – Lautaro Lobo Apr 7 at 21:07
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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