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

Official answer is the first one.

---

What is the final ans A or B ?

---

http://univ.tifr.res.in/gs2018/Files/GS2016_QP_CSS.pdf

part b) question 7:

Answer is A

---

We can also prove it using calculus :-

2 Functions $f$ and $g$ are  asymptotically equivalent or similar i.e. $f\sim g$ as $n\rightarrow \infty$  iff $\frac{f}{g} \rightarrow 1$

So, if we are able to prove that $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} = 1$  , then we can say that $f$ and $g$ are asymptotically equivalent means they have the same growth rate since they are similar.

here , $n = m! $ , According to Stirling's Approximation ,   $m!$ $\approx$ $m^{m}$

So, here ,

$\frac{logn}{log log n} = \frac{logm^{m}}{loglog(m^{m})} = \frac{mlogm}{log(mlogm)}= \frac{mlogm}{logm+loglogm}$

So, here , we have 2 functions $f(m) = m$ and $g(m)=\frac{mlogm}{logm+loglogm} $

 Now, we have to check whether , $\lim_{m\rightarrow \infty }\frac{f(m)}{g(m)} = 1$ or not.

So, $\lim_{m\rightarrow \infty }\frac{f(m)}{g(m)}= \frac{m}{\frac{mlogm}{logm+loglogm}} = \frac{m(logm+loglogm)}{mlogm} = \frac{logm+loglogm}{logm}$

Now , Using $L'H\hat{o}pital's \;Rule$ ,

= $\frac{\frac{1}{m}+\frac{1}{logm}*\frac{1}{m}}{\frac{1}{m}} = \frac{logm+1}{logm}$

Again , Using $L'H\hat{o}pital's \;Rule$

$= \frac{logm+1}{logm} = \frac{\frac{1}{m}}{\frac{1}{m}} = 1$

So, Now , we have proved that $\lim_{m\rightarrow \infty }\frac{f(m)}{g(m)} = 1$.

It means Functions f(m) =m and $g(m)=\frac{mlogm}{logm+loglogm}=\frac{logn}{loglogn}$ are asymptotically equivalent or similar functions.

So, we can write it as $f=O(g)$ and $g=O(f)$ which implies $f= \Theta (g)$.

So, Answer should be (A)

--------------------------------------------------------------------------------------------------------------------

Edit (03/05/2022): There is small mistake which is mentioned in below comment.

Writing $m! \approx m^\left(m+\frac{1}{2}\right)e^{-m}$ is correct, not $m! \approx m^m$ 

because According to Stirling's Approximation, $n! \sim \sqrt{2 \pi} n^\left(n+ \frac{1}{2}\right)e^{-n}$ 

Rest things are correct.

Considering $m! \approx m^\left(m+\frac{1}{2}\right)e^{-m}$, if we take log

$\log (m!) \sim \log (m^\left(m+\frac{1}{2}\right)e^{-m}) = (m + \frac{1}{2}) \log m - m \log e = m \log m + \frac{1}{2} \log m - m \log e$

So, $\log (m!) = \Theta (m \log m)$

---

@ankitgupta.1729 nice approach .

---

@ankitgupta.1729 pretty well approach man ! now we can here easily distiguish between thetha and omega that was look very hard previouly....

---

Ankit's approach is solid, just wanted to point out that the limit can be any constant value, not just 1, for both functions to be asymptotically equivalent.

See definition 2: https://math.psu.edu/sites/default/files/public/migration/141rates1.pdf

Edit: @ankitgupta.1729 says that "growth rate" and "asymptotic growth rate" are different, and that although in case of former any constant works, and former implies latter, but for latter the constant should be 1. See: https://en.wikipedia.org/wiki/Asymptotic_analysis#Definition

---

@ 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