5
$\begingroup$

How does $Θ(\log(n!))=Θ(\log(n^n)$?

I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the following:

$$\lim_{x\to \infty}\left(\frac{\log_2(x^x)}{\log_2(x!)}\right)=\infty. $$

So how could there be constants such that $Θ(\log(n!))=Θ(\log(n^n))$?

Where has my understanding gone wrong?

$\endgroup$
7
$\begingroup$

As a matter of fact, $$\lim_{x\to \infty}\frac{\log_2(x^x)}{\log_2(x!)}=1.$$ So there is no problem to reconcile.

Looking at the first revision of the question, it seems to me that you are confused about the fact that $\frac{n^n}{n!}$ has different behaviour from $\frac{\log n^n}{\log n!}$: $$\lim_{n\to+\infty}\frac{n^n}{n!}=+\infty,\qquad\text{while}\qquad\lim_{n\to+\infty}\frac{\log(n^n)}{\log(n!)}=1<+\infty.$$ There is no problem with this. Unboundedness of ratios of functions is not preserved by applying arbitrary functions such as $\log$, because $\exp$ (the inverse of $\log$) is not polynomially bounded. For a simpler example, $$\lim_{n\to+\infty}\frac{n^2}{n}=+\infty,\qquad\text{while}\qquad\lim_{n\to+\infty}\frac{\log(n^2)}{\log(n)}=2<+\infty.$$

In general, a function $h\colon\mathbb R_{>0}\to\mathbb R_{>0}$ satifies the condition that $$\limsup_{n\to+\infty}\frac{f(n)}{g(n)}<+\infty\implies\limsup_{n\to+\infty}\frac{h(f(n))}{h(g(n))}<+\infty$$ for all $f,g\colon\mathbb N\to\mathbb R_{>0}$ if and only if there exists a constant $c$ such that $$y\le2x\implies h(y)\le ch(x)\tag1$$ for all $x,y\in\mathbb R_{>0}$. For example, (1) holds for all function of the form $h(x)=x^\alpha$ for some $\alpha$. On the other hand, any function $h$ satisfying (1) is polynomially bounded, specifically, $h(x)=O(x^{\lceil\log_2c\rceil})$.

$\endgroup$
0
2
$\begingroup$

$$\log (n!)=\log\left(\prod_{i=1}^{n}i\right)$$ $$=\log(1)+\log(2)+\dots+\log n$$ $$=\sum_{i=1}^{n}\log i\leq n\log n.$$ $$\sum_{i=1}^{n}\log i=\sum_{i=1}^{\frac{n}{2}}\log i+\sum_{i=\frac{n}{2}+1}^{n}\log i$$ $$\geq\frac{n}{2}\log(\frac{n}{2})=\Theta(n\log n).$$

Since $$\log n^n=n\log n$$ $$\implies \log (n!)=\Theta(\log n^n).$$

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