$\ln(x)$ and Big O notation

4.3k Views Asked by At

I have tried to assert that $\ln(x)=O(x^0)$ a few times, but it seems fairly obvious that this statement should be false, and so I've been faced with some rightful speculation.

My reason is that

$$\ln(x)=\lim_{k\to0}\frac{x^k-1}{k}=O(x^0)?$$

But if not, then I ask

What is the smallest value of $k$ for $\ln(x)=O(x^k)?$ A proof would be nice, and possibly some cleanuping if my notation is used incorrectly.

2

There are 2 best solutions below

9
On BEST ANSWER

The first point is: when you use asymptotic notations, you need to specify with regard to what point the asymptotics is taken. Here, it looks like this is when $x\to 0^+$; note that this could have equally been $x\to\infty$, so specifying it is required.

Now, you have that for any fixed $\alpha > 0$, $$ \ln x = O(x^{-\alpha}) $$ when $x\to 0^+$, since $\left\lvert x^\alpha \ln x\right\rvert\xrightarrow[x\to0^+]{} 0$. Yet, this does not "go to the limit": there is no minimum $\alpha\geq 0$ for which this holds.


Parenthesis: you have $\ln x = x^{\frac{\ln\ln x}{\ln x}}$, so you could technically write $\ln x = \Theta(x^{\frac{\ln\ln x}{\ln x}})$... but note that this means "taking $\alpha = \alpha(x) = \frac{\ln\ln x}{\ln x}$."

12
On

For $r>0$ take $M>1$ such that $1/M<r.$ For $y>M$ we have $$0<\ln y=\int_1^y (1/z)\;dz= \int_1^M(1/z)\;dz+\int_M^y(1/z)\;dz=$$ $$=\ln M+\int_M^y(1/z)\;dz<\ln M+\int_M^y(1/M)\;dz=\ln M+(y-M)/M.$$ $$\text { So, }\quad 0<(\ln y)/y<(\ln M)/y+(1-M/y)/M.$$ Therefore $$0\leq \sup_{x\geq y}\;(\ln x)/x\leq \sup_{x\geq y}(\;(\ln M)/x+(1-M/y)/M\;)=$$ $$=(\ln M)/y+(1-M/y)/M.$$ $$\text {Therefore, }\quad 0\leq \lim_{y\to \infty}\sup_{x\geq y}\;(\ln x)/x\leq$$ $$\leq \lim_{y\to \infty}\;(\ln M)/y+(1-M/y)/M=1/M<r.$$ Since $r$ can be as small as desired, we have therefore $\lim_{y\to \infty}(\ln y)/y=0.$

For positive $a,b$ we have $$(\ln y)^a/y^b=((\ln y)/y^{b/a})^a=(((a/b)\ln y^{b/a})/y^{b/a})^a.$$ Let $z=y^{b/a}.$ Then $z\to \infty$ as $y\to \infty$ and we have $$(\ln y)^b/y^a=((a/b)^a\cdot ((\ln z)/z))^a\to 0$$ as $y$ (and $z$) go to $\infty.$

In particular with $a=1$ and $b>0$ we have $\lim_{y\to \infty}(\ln y)/y^b=0.$ So as $y\to \infty$ we have $\ln y=O(y^b)$ for any $b>0. $

Actually we have $\ln y=o(y^b)$ as $y\to \infty$ for any $b>0$ because $\lim_{y\to \infty}(\ln y)/y^b=0.$

For $0<y<1$and $y\to 0$ let $x=1/y.$ Then $|\ln y|/y=x\ln x$ and use the above inequalities.