Small o notation PROOF

Question

It's probably a vey silly question, but I'm confused. I should proof the small o notation with lim but i don´t know how

$(\ln n)^a = o(n^b )$ how do i solve this and do i need to proof it for $a<b$, $a>b$ or $a=b$ ?

Answer 1

I think that $a,b>0$. You have to show that $\frac{( \ln n)^a}{n^b} \to 0 $ as $ n \to \infty$. If $t:= \ln n$, then we have to show that

$\frac{t^a}{e^{tb}} \to 0$ as $ t \to \infty$. To this end let $ m \in \mathbb N$ with $m>a$. Then $e^{tb} \ge \frac{t^mb^m}{m!}$, hence

$ 0 \le \frac{t^a}{e^{tb}} \le \frac{t^a}{e^{tb}} \le \frac{m!}{b^m}\frac{1}{t^{m-a}}$

Your turn !

Answer 2

Correct notation is $f(n) = o(g(n))$. Writing equality $f(n) = o(g(n))$ means that $ f(n) $ live in set $o(g(n))$. Here, $$ o(g(n))\mathop{=}^{\mathrm{def}}\left\{f(n): \lim_{n\to\infty}\frac{f(n)}{g(n)}=0\right\} $$ I believe your question is to find the lowest value of $ b> 0 $ such that $(\ln n)^a = o(n^b )$ for $a>0$, that is, to find the lowest value of $ b> 0 $ such that $$ \lim_{n\to\infty}\frac{(\ln n)^a}{n^b}=0. $$ Correct? To prove this you should use the fact that for all $c>0$ we have $$ \lim_{n\to\infty} n^c/e^n=0. $$