1
$\begingroup$

I need to compare (asymptoticly) between $\left ( \frac{\ln n +4 \ln\ln n}{\ln n} \right )^{\ln n}$ and $16^{\ln\ln n}$. The options are $\Theta , \omega, o$. My work so far:

I denoted $t_n=\ln n$ to make things cleaner.

The first sequence is $\left ( 1+\frac{4 \ln t_n}{t_n} \right )^{t_n}$. It looks a bit like the sequence that can be used to define $e^x$: $(1+\frac{a}{n})^n\rightarrow e^a$ but I don't know what to do about it.

The second sequence is $16^{\ln t_n}=e^{\ln 16 \ln t_n}=(e^{4\ln t_n})^{\ln 2}$.

Do you see a way to continue?

$\endgroup$
1
$\begingroup$

A general idea: convert everything to exponential form. "Apples-to-apples." (Plus, things are much easier to manipulate and recognize from there.)

Let us see how that would go.

First attempt: $$ \left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} = e^{t_n \ln\left(1+\frac{4\ln t_n}{t_n}\right) } $$ Now, if remembering the useful inequalities $\ln(1+u)\leq u$, you get $$ \left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} \leq e^{t_n\frac{4\ln t_n}{t_n} } = e^{4\ln t_n } = t_n^4. $$ On the other hand, $$ 16^{\ln t_n} = e^{\ln 16 \ln t_n} = t_n^{\ln 16} $$ and $\ln 16 \simeq 2.77$. Sadly, this does not tell you immediately what you want (as for the first, we used an upper bound).

But we can improve a bit the first bound! From $$ \left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} = e^{t_n \ln\left(1+\frac{4\ln t_n}{t_n}\right) } $$ we now use the fact that $\ln(1+u)=u+O(u^2)$ when $u\to 0$, and that $\frac{\ln t_n}{t_n}\xrightarrow[n\to\infty]{} 0$: $$\begin{align} \left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} &= e^{t_n \ln\left(1+\frac{4\ln t_n}{t_n}\right) } = e^{t_n \left(\frac{4\ln t_n}{t_n}+O\left(\frac{\ln^2 t_n}{t_n^2}\right)\right) } = e^{{4\ln t_n} +O\left(\frac{\ln^2 t_n}{t_n}\right) }\\ &= e^{{4\ln t_n} +o(1) } = t_n^4\cdot e^{o(1) } \end{align}$$

so this tells you immediately that $$\left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} = \Theta(t_n^4) \tag{1}$$ while $$16^{\ln t_n} = t_n^{\ln 16} < t_n^3 \tag{2}$$ since $t_n\xrightarrow[n\to\infty]{} \infty$ and $\ln 16 < 3$. Therefore, $$ \left(1+\frac{4\ln t_n}{t_n}\right)^{t_n} = \omega\left(16^{\ln t_n}\right) $$ when $n\to\infty$.

$\endgroup$
  • $\begingroup$ Note that the conclusion on $t_n^4$ for the first is basically validating yourintuition about "$(1+a/t_n)^{t_n}$." But this argument cannot be made directly, as it is simply not true that $(1+a/t_n)^{t_n}\simeq e^a$ when $a$ is not a constant. (This is only true for some particular ranges of $a$.) $\endgroup$ – Clement C. Aug 5 '16 at 15:04
1
$\begingroup$

We have that $$a_n:=\left ( \frac{\ln n +4 \ln\ln n}{\ln n} \right )^{\ln n}=\left ( 1+\frac{4 \ln\ln n}{\ln n} \right )^{\ln n}=\exp\left(\ln n \ln\left ( 1+\frac{4 \ln\ln n}{\ln n} \right )\right)\\ =\exp\left(\ln n \frac{4 \ln\ln n}{\ln n} +\ln n\ o\left(\frac{4 \ln\ln n}{\ln n}\right )\right)=\exp\left(4 \ln\ln n + o\left(\ln\ln n\right )\right).$$ On the other hand $$b_n:=16^{\ln\ln n}=\exp\left(4\ln 2\ln\ln n\right).$$ Therefore, as $n\to +\infty$, $$\frac{a_n}{b_n}=\exp\left(4(1-\ln(2)) \ln\ln n +o\left(\ln\ln n\right )\right)\to +\infty$$ because $\ln(2)<1$. We conclude that $a_n$ goes faster to infinity than $b_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.