In the paper Decomposable Searching Problems I. Static-to-Dynamic Transformations by Bentley and Saxe, the authors state without proof that
$$\sqrt[n]{n!} \sim {\frac{n}{e}}\text.$$
I have a line of reasoning below that I think correctly proves this, but I'm a bit shaky about whether I can apply tilde approximations this way. Is this reasoning correct?
Using Stirling's approximation, we know that
$$n! \sim \left(\frac{n}{e}\right)^n \sqrt{2\pi n}\text.$$
Taking $n$th roots then gives
$$\sqrt[n]{n!} \sim \left( \frac{n}{e} \right) \sqrt[2n]{2 \pi n} \sim \frac{n}{e}\text.$$
The step I'm uncomfortable about is whether I can take $n$th roots of both sides of the tilde expression. This feels like it "ought" to work, but I've been surprised by tilde expressions in the past and wouldn't want to bet the farm on it. 🙂
Best Answer
Suppose that $a_n\sim b_n$ as $n\to +\infty$. This means, by definition, that, in particular, $$ \frac{1}{2}<\frac{a_n}{b_n}<\frac{3}{2} $$ for all sufficiently large $n$. Taking $n$th roots and using the squeeze theorem shows that $\sqrt[n]\frac{a_n}{b_n}=\frac{\sqrt[n]{a_n}}{\sqrt[n]{b_n}} \to 1$, i.e., $\sqrt[n]{a_n} \sim \sqrt[n]{b_n}$ as $n\to +\infty$.
You can apply this observation to $a_n=n!$ and $b_n=\left( {\frac{n}{\mathrm{e}}} \right)^n \sqrt {2\pi n}$.