retagged by
5,967 views
50 votes
50 votes

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)$
retagged by

6 Answers

Best answer
23 votes
23 votes
$$\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$
edited by
4 votes
4 votes

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

3 votes
3 votes
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
Answer:

Related questions