# Big O, Little O and Logarithm Integral

• September 25th 2010, 11:24 AM
DwProd
Big O, Little O and Logarithm Integral
Hello everyone,

I've spent the last hours trying to understand Big O and little O notations in depth. Usually the limit of the quotient method works but here, I'm dealing with integrals which seems to make things harder.

integral(dt/ln(t),t=2..sqrt(x))=O(sqrt(x)) when x->+∞
integral(dt/(ln(t))^2,t=sqrt(x)..x)=o(integral(dt/ln(t),t=sqrt(x)..x) when x->+∞

I'd really appreciate some tips or the general method on proving these two assertions. Sorry for not knowing Latex, I'll get to it soon ^^

Thanks for any help!
• September 25th 2010, 11:47 AM
CaptainBlack
Quote:

Originally Posted by DwProd

integral(dt/ln(t),t=2..sqrt(x))=O(sqrt(x)) when x->+∞

Put:

$I(x)=\displaystyle \int_{t=2}^{\sqrt{x}}\dfrac{1}{\ln(t)}\;dt$

Now $\ln (t)$ is a positive increasing function on $(1,\infty)$ so $1/\ln(t)$ is decreasing so:

$I(x)<\displaystyle \int_{t=2}^{\sqrt{x}}\dfrac{1}{\ln(2)}\;dt=\dfrac{ 1}{\ln(2)} \times (\sqrt{x}-2)$

and you should be able to complete the proof from there.

CB
• September 25th 2010, 11:53 AM
DwProd
Yes that is what I've been able to do so far but I'm not sure this allows me to verify the first assertion. I think it has to do with the
∃x0>0 ∃M>0 ∀x>x0 abs(f(x))<M*abs(g(x)) => f(x)=O(g(x)) but I'm not even sure it is a proper definition and why the condition x->+∞ is useful here. Thanks for your answer by the way!
• September 25th 2010, 11:59 AM
CaptainBlack
Quote:

Originally Posted by DwProd
integral(dt/(ln(t))^2,t=sqrt(x)..x)=o(integral(dt/ln(t),t=sqrt(x)..x) when x->+∞

Let:

$\displaystyle I(x)=\int_{\sqrt{x}}^x \dfrac{1}{(\ln(t))^2}\; dt$

again we observe that on $(1,\infty)$ $1/\ln(t)$ is decreasing so for $t>\sqrt{x}$:

$\dfrac{1}{(\ln(t))^2}<\dfrac{1}{\ln(\sqrt{x})}\tim es \dfrac{1}{\ln(t)}$

CB
• September 25th 2010, 12:14 PM
DwProd
Ok I think I get it, I can just create the quotients with those inequalities (since everything is positive and ≠ 0) and then just use the Squeeze theorem.
If this is all I need to do, please just confirm so that I can put the little [SOLVED] :D Thank you very much for your help CaptainBlack!
• September 25th 2010, 01:24 PM
CaptainBlack
Quote:

Originally Posted by DwProd
Ok I think I get it, I can just create the quotients with those inequalities (since everything is positive and ≠ 0) and then just use the Squeeze theorem.
If this is all I need to do, please just confirm so that I can put the little [SOLVED] :D Thank you very much for your help CaptainBlack!

I don't think you need the squeeze theorem just the definition of big-O and little-o notation

CB