4,838 views

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

1. $m = \Theta (\log n / \log \log n)$
2. $m = \Omega (\log n / \log \log n)$ but not $m = O(\log n / \log \log n)$
3. $m = \Theta (\log^2 n)$
4. $m = \Omega (\log^2 n)$ but not $m = Ο(\log^2 n)$
5. $m = \Theta (\log^{1.5} n)$

edited by

this is basic math, i found this is useful rather than putting values, nice approach but how judge omenga and theta here , it's bit confusing ?

and one more thing if we put log(logm) = 0  then m = log(n) / [log(logn) - log(logm)] should be max not min.Hence This case doesn't distinguish between omega and  thetha isn't it ?

Super
Knowing the fact that sterling's approximation, $\log(n!) = \Theta(n \log n)$ i.e both $O(n \log n)$ and $\Omega(n \log n)$makes this question easier.

$$\begin{array}{|l|l|} \hline \textbf{m} & \text{n=m!} & \text{\log n / \log \log n} \\\hline \text {4} & \text{24} & \text{4/2 = 2} \\ \text {6} & \text{720} & \text{9/3 = 3} \\ \text {8} & \text{720\times56} & \text{15/3 = 5} \\ \text {10} & \text{720\times56\times90} & \text{21/4 = 5} \\\hline \end{array}$$If we see, $m$ is growing at same rate as $\log n / \log \log n$.
Correct Answer: $A$
by

edited

Is there any shorter process to do this type of problems?
and Why don't we check this problem with option (c), (d) or (e)?

edited

@prithatiti

For shorter process, I think you can do what arjun sir did but problem is how much big 'n' can be. If you get $\lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = c$ where $c>0$ and limit exists then you can easily say that $f(n) = \Theta (g(n))$. So, it should be both $\mathcal{O}(g(n))$ and $\Omega(g(n)).$ Sometimes, manipulation in functions might work like this  to solve these type of questions. So, if you have 2 functions like $2^{\lg 2n^{10}}$ and $n^{10}$. With some manipulation, you have changed $n^{10}$ to $2^{\lg n^{10}}$ then we can say, both functions have same growth rate and can be written in theta notation to each other.

Here, options (c), (d) and (e) can be easily eliminated.

$\log^2 n \approx (\log m^m)^2 = (m\log m)^2 = m^2 \log^2m$. Here, $m \in \mathcal{O}(m^2log^2m)$ but $m \notin \Omega(m^2log^2m)$.

Same thing you can do for function $\log^{1.5} n.$ $n=m!$
$n = m^m$
$logn = mlogm$
$m = \frac{logn}{logm}$
So, $m< logn$, hence $m = O(logn)$ from here $logm = loglogn$
$m = omega( \frac{logn}{loglogn})$. This is asympotically tight lower bound.
But, we can’t predict upper bound.
So, I'm not sure if answer is (A) or (B).

### 1 comment

$\color{red}{n = m^m}$ This is wrong. Infact $m!$ is strictly lesser than $m^m$ i.e.  $m! < m^m$ which means  $m! = \text{small-oh}( m^m)$.

I find this way easier to understand:

assuming all logs are of base m.

than logn=logm^m=m

and loglogn=logm.

evaluate all aymptotaics than i m finding B to be true

option B is the ans
by