patternMinor
How does $Θ(\log(n!))=Θ(\log(n^n)$?
Viewed 0 times
logdoeshow
Problem
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?
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?
Solution
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!)}=10}\to\mathbb R_{>0}$ satifies the condition that
$$\limsup_{n\to+\infty}\frac{f(n)}{g(n)}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})$.
$$\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!)}=10}\to\mathbb R_{>0}$ satifies the condition that
$$\limsup_{n\to+\infty}\frac{f(n)}{g(n)}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})$.
Context
StackExchange Computer Science Q#143524, answer score: 7
Revisions (0)
No revisions yet.