Question on Asymptotic Function.

Question

Question

Let $n = m!$. Which of the following is TRUE?

$a)m = \Theta (\frac{\log n}{\log \log n})$

$b)m = \Omega (\frac{\log n}{\log \log n})$ but not $m = O(\frac{\log n}{\log \log n})$

$c)m = \Theta (\log^2 n)$ $m = \Omega (\log^2 n)$ but not $m = Ο( (\log^2 n)$

$d)m = \Theta (\log^{1.5} n)$

Let me Clear that this is not a homework question, i have learnt asymptotic growth and trying to solve some good question.During Practicing, i found this beautiful question but i am stuck at one point and unable to move on to conclude the answer.

My approach

Given $n = m!$

$\Rightarrow \log n=(\log m!)=m \log m$

$\Rightarrow m=\frac{\log n }{\log m}$

I am stuck how to move forward .What value should i give to $\log m$?

Please help

Answer 1

The first issue with what you wrote is that you write an equality instead of an asymptotic equivalence: you cannot write $\log m! = m\log m$. You can write $$\log m! \operatorname*{\sim}_{m\to\infty} m\log m$$, which is equivalent to writing $\log m! = m\log m + o(m\log m)$; or, more precise, $$ \ln m! = m\ln m - m + O(\log m) $$ (this is Stirling's approximation).

---

Now, let us start from there. Since $n=m!$, we have $$ \log n = m\log m +o(m\log m) \tag{1} $$ by the above. Let us write $m = f(n)\log n$ for some $f>0$ we are trying to figure out (asymptotically). (1) becomes $$ \log n = f(n)\log n\log f(n) + f(n)\log n\log \log n +o(f(n)\log n\log (f(n)\log n)) $$ or equivalently $$ 1 = f(n)\log f(n) + f(n)\log \log n +o(f(n)\log (f(n)\log n)) \tag{2} $$ From this, it is clear that we must have $f(n)=o(1)$ (as otherwise $f(n)\log \log n$ is unbounded). That allows us to simplify (2) as $$ 1 = o(1) + f(n)\log \log n +o(f(n)\log\log n) \tag{3} $$ which implies (for the equality to hold) that we must have $f(n)\log \log n = 1+o(1)$, and thus $$f(n) \operatorname*{\sim}_{n\to\infty} \frac{1}{\log\log n}\,.$$

Putting it all together, $$ \boxed{m \operatorname*{\sim}_{n\to\infty} \frac{\log n}{\log\log n}\,.} $$

Answer 2

Well, we first observe that (c) is incorrect because $m = \mathcal{O}(m^2 \log^2 m) = \mathcal{O}((m \log m)^2) = \mathcal{O}(\log^2 m!) = \mathcal{O}(\log^2 n)$ using the fact that $\log m! = \Theta(m \log m)$.

Similarly, one can show $\Theta(\log^{1.5}n) = \Theta(m^{1.5} \log^{1.5} m)$ using similar method. But we know $m = o(m^{1.5} \log^{1.5} m)$ so (d) cannot be true. Therefore, the right answer should be (a) or (b).

Now we try to evaluate $$\Theta\left(\frac{\log n}{\log \log n}\right) = \Theta\left(\frac{\log m!}{\log \log m!}\right)$$

Since $\log m! = \Theta(m \log m)$, by definition, there is $C_1, C_2 > 0, N_1 \in \mathbb{N}$ such that for all $m \ge N_1$ $$C_1 m \log m \le \log m! \le C_2 m \log m$$ Taking $\log$ on the equation, we have that for all $m \ge N_1$ $$\log(C_1 m \log m) \le \log \log m! \le \log(C_2 m \log m)$$ Applying the $\log$ laws give $$\log C_1 + \log m + \log \log m \le \log \log m! \le \log C_2 + \log m + \log \log m$$ Clearly $$\log m \le \log C_1 + \log m + \log \log m$$ On the other hand, since $\log C_2 + \log \log m = \mathcal{O}(\log m)$, we can find $C_3 > 0, N_2 \in \mathbb{N}$ such that for all $m \ge N_2$ $$\log C_2 + \log \log m \le C_3 \log m$$ Now let $N = \max\{N_1, N_2\}$. Then for all $m \ge N$, we have $$\log m \le \log \log m! \le (C_3 + 1) \log m$$ Therefore, by definition, $$\log \log m! = \Theta(\log m)$$ Finally, it is party-time, $$\Theta\left(\frac{\log n}{\log \log n}\right) = \Theta\left(\frac{\log m!}{\log \log m!}\right) = \Theta\left(\frac{m \log m}{\log m}\right) = \Theta(m)$$ Now clearly $$m = \Theta(m) = \Theta\left(\frac{\log n}{\log \log n}\right)$$ So (a) is correct!