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

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

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.

• Possibly typo in very first limit: answer is $0$, not $+\infty$. Dec 15 '20 at 22:30
• @zkutch, thanks! Dec 15 '20 at 22:57

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

• This is elegant! Nov 10 '20 at 17:13
• Thanks @Steven. I was hoping that someone would appreciate it Nov 10 '20 at 17:42