algorithms - Question on Asymptotic Function.

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

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