TIFR CSE 2016 | Part B | Question: 7

Question

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

• A. $m = \Theta (\log n / \log \log n)$
• B. $m = \Omega (\log n / \log \log n)$ but not $m = O(\log n / \log \log n)$
• C. $m = \Theta (\log^2 n)$
• D. $m = \Omega (\log^2 n)$ but not $m = Ο(\log^2 n)$
• E. $m = \Theta (\log^{1.5} n)$

Comments

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.

Answer 1

$$\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$\times$56} & \text{15/3 = 5} \\  \text {10} &  \text{720$\times$56$\times$90} & \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$

Comments

@ ankitgupta.1729

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)?

---

@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.$

---

Answer 2

$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).

Comments

$\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)$.

See here https://math.stackexchange.com/a/2431263/309722

Answer 3

I find this way easier to understand:
 

 

Answer 4

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