Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$

Question

I am trying to proof $f\in o(g)$

Let be $r,p\in \mathbb{R}$ with $p>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$

I have already proofed that $ln(n)\in o(n)$ via l'Hospital $\lim\limits_{n\to \infty}\frac{\frac{1}{x}}{1}=0\Longrightarrow \lim\limits_{n\to \infty}\frac{ln(n)}{n}=0\Longleftrightarrow ln(n)\in o(n)$

I tried substituting n with ln(n) to recieve $\forall c>0 \exists n_0 \forall n\geq n_0 : ln(ln(n))\leq cln(n)$
Then i tried splitting $c=\frac{a}{b}$ to get $\forall \frac{a}{b}>0\exists n_0 \forall n\geq n_0 : ln(ln(n)) \leq \frac{a}{b}ln(n)$
With this information i said, that $\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))=b*ln(ln(n))\leq \frac{a}{b}*\frac{b}{a}*\frac{a}{b}*b*ln(n)=\frac{a}{b}*b*ln(n)=a*ln(n)$
to conclude $ln(n)^b=e^{\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))}\leq e^{\frac{b}{a}*b*ln(n)}=e^{b*ln(n)}=n^a$

At this point i realized a huge problem. I assumed $\frac{a}{b}$ to be positive. But i need it to work for r and p, where only p is known to be postive, which in the other hand means, that r can be negative, what would make $\frac{p}{r}$ negative.

It means that my approach is propably not working a

Answer 1

You just need to show that $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = 0. $$

This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$.

For $r>0$, you can use l'Hôpital's rule $\lceil r \rceil$ times to obtain: $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = \lim_{n \to \infty} \frac{r \log^{r-1} n}{pn^{p}} = \dots = \lim_{n \to \infty} \frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i) \cdot \log^{r-\lceil r \rceil} n}{p^{\lceil r \rceil} n^{p}} \\ = \frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}\cdot \lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} =0, $$

where $\frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}$ is a positive constant and $ \lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} $ is equal to $0$ since it falls into the previous case.

Answer 2

Let's consider only $r>0$. For $\ln(n)^r \in o(n^p),p>0$ is enough to show $\ln(n) \in o(n^\alpha)$, for $\frac{p}{r}=\alpha>0$, because $\frac{\ln(n)^r}{n^p} =\left(\frac{\ln(n)}{\sqrt[r]{n^p}}\right)^r$ and $r$ power is continuous function. So we come to limit

$$\lim\limits_{n \to \infty}\frac{\ln(n)}{n^\alpha}=\lim\limits_{n \to \infty}\frac{\frac{1}{n}}{\alpha n^{\alpha-1}}=\lim\limits_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$