1
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Possibly typo in very first limit: answer is $0$, not $+\infty$. $\endgroup$
    – zkutch
    Dec 15, 2020 at 22:30
  • $\begingroup$ @zkutch, thanks! $\endgroup$
    – Steven
    Dec 15, 2020 at 22:57
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This is elegant! $\endgroup$
    – Steven
    Nov 10, 2020 at 17:13
  • $\begingroup$ Thanks @Steven. I was hoping that someone would appreciate it $\endgroup$
    – zkutch
    Nov 10, 2020 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.