How to find the relative order between two functions $f(n)$ and $g(n)$?

109 Views Asked by At

I have two functions: $$f(n) = n^{a-1}$$

$$g(n) = 2^{\sqrt{\ln(n)}}$$

I know that I can use the limit rule which involves calculating the limit $\dfrac{n^{a-1}}{2^{\sqrt{\ln(n)}}}$

Because it's not obvious where the limit is trending towards we have to use the L'Hôpital's rule. $f(n)$ complicates things because it doesn't give a simple derivative. Am I doing it wrong?

I thought I pretty much had to use the L'Hôpital's rule because considering that $\ln(n)$ is increasing we have $2^∞$. which seems to be indeterminate like $1^{∞}$. Maybe my assumption is wrong?

1

There are 1 best solutions below

0
On

I claim that for large enough $n$, $f(n) \gt g(n)$ if $a \gt 1$, while $g(n) \gt f(n)$ if $a \le 1$

The second part is the easy one. If $a \le 1, f(n) \le 1$ and $g(n) \to \infty$

For the first, we note that $\ln n=\ln 2 \cdot \log_2 n, 2^{\ln n}=2^{\ln 2\cdot \log_2 n}=n^{\ln 2}, 2^{\frac {\ln n}k}=n^{\frac{\ln 2}k}$

For any natural $k$, when $n \gt e^{k^2}, \ln n \gt k^2$. When $n$ is that large $\sqrt{\ln n} \lt \frac {\ln n}k$. In that case $g(n)=2^{\sqrt{\ln n}}\lt 2^{\frac{\ln n}k}=n^{\frac{\ln 2}k}$

Given $a \gt 1$, choose $k$ large enough that $\frac 1k \lt a-1$. Then for $n \gt e^{k^2}\quad f(n) \gt g(n)$