1. ## Prove a theorem

Hello.It is my first time visiting this forum and I hope you can help me.
I need to prove a theorem and i hope you will help me.

Theorem:

lgn is in o(n^(alfa)) for any alfa > 0.That is ,the log function grows more slowly than any power of n(including fractional powers).

I dont know how to prove this.Please help me.

2. Originally Posted by drilli
Hello.It is my first time visiting this forum and I hope you can help me.
I need to prove a theorem and i hope you will help me.

Theorem:

lgn is in o(n^(alfa)) for any alfa > 0.That is ,the log function grows more slowly than any power of n(including fractional powers).

One way to do it is to prove that $\displaystyle{\lim_{x\to\infty}\frac{\ln x}{x^\alpha}=0\,,\,\,\forall \alpha >0}$ . You may want to use L'Hospital here...

Tonio

3. THank you.
Well to prove this lim is easy and i just proved it but why do you think this is a proof of that theorem .Could you please explain me with a few words what does it mean if this lim is 0.What is the relationship of this limit with the theorem ?

4. Originally Posted by drilli
THank you.
Well to prove this lim is easy and i just proved it but why do you think this is a proof of that theorem .Could you please explain me with a few words what does it mean if this lim is 0.What is the relationship of this limit with the theorem ?
The limit means that for any $\varepsilon>0$ there exists an $N_{\varepsilon}$ such that:

$\left| \dfrac{\ln(n)}{n^{\alpha}} \right|<\varepsilon$

for all $n>N_{\varepsilon}$ and the little-o notation conclusion follows imeadiatly, since we now have:

for any $\varepsilon>0$ there exists an $N_{\varepsilon}$ such that:

$\left| {\ln(n)} \right|<\varepsilon |n^{\alpha}|$

for all $n>N_{\varepsilon}$

(Little-o notation is just another way of expressing that the limit of the ratio is zero)

(The difference between ln, lg and any other based logs here is irrelevant as this amounts to a multiplicative constant which is washed out in the asymptotic/limit argument)

CB

5. That is the proof. If the theorem is correnct, then the log function grows more slowly than any power of n would imply that as x becomes big, x^alpha will be bigger than lnx, and as x becomes bigger, the difference between x^alpha and lnx will be even bigger. So if that was the case, the limit of lnx/x^alpha would tend to zero as you are dividing a smaller number to a very big number. So you check whether this is the case, and the lim = 0 tells you so.