Asymptotic evaluation

Question

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?

Answer 1

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

Answer 2

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