Is $\sqrt{n}$ polynomially larger than $\log{n}$?

Question

For functions $f(x)$ and $g(x)$, $f(x)$ is polynomially larger than $g(x)$ if $f(x)$ is asymptotically larger than $g(x)$ by a factor of $n^{\epsilon}$ for some constant $\epsilon > 0$.

$\lim_{n \rightarrow \infty} \frac{\sqrt{n}}{\log{n}} = \infty$ tells me that $\sqrt{n}$ is asymptotically larger than $\log{n}$, but I am stuck determining whether or not it is polynomially larger. If $\sqrt{n}$ is polynomially larger than $\log{n}$, how can I find a factor $n^{\epsilon}$?

Answer 1

Since both the numerator and denominator go to $\infty$ as $n \to \infty$, we may apply de l'Hôpital's rule: $$\lim_{n \to \infty} \frac{\sqrt{n}}{\log n} = \lim_{n \to \infty} \frac{\frac{1}{2\sqrt{n}}}{\frac{1}{n}} = \lim_{n \to \infty} \frac{\sqrt{n}}{2} = \lim_{n \to \infty} \frac{n^{1/2}}{2}$$ This tells you that you can pick $\epsilon \in (0,1/2)$.

Answer 2

It is also true that $$\lim_{n\to\infty}{\frac{n^\frac14}{\log n}}=\infty$$ Thus $$\lim_{n\to\infty}{\frac{n^\frac12}{n^\frac14\log n}}=\infty$$