If $x^a<\ln(x)<x^b$, then how are $a$ and $b$ bounded?

51 Views Asked by At

Question: Let $x^a<\ln(x)<x^b$, for sufficiently large $x$. How large can $a$, and how small can $b$ be, such that this inequality stays true?

Context: While reading about computational complexity, I found a lot of complexities expressed in terms of $\ln n$. But it's tricky to relate this to complexities such as $n^{1.2}$. So I tried to find a way of expressing $\ln(x)$ as $x^a$.

Attempt: Clearly $1<\ln(x)<\sqrt{x}$, so $x^0<\ln(x)<x^{0.5}$. Hence, the maximum possible value of $a$ is at least $0$, while $b$ has a minimum of at most $0.5$.

But can $a$ be made any larger or $b$ any smaller?

1

There are 1 best solutions below

8
On BEST ANSWER

We know that

$$x-1\ge\ln(x)$$

Substituting $x=t^a$ gives us

$$t^a-1\ge a\ln(t)$$

Assuming $a>0$,

$$\frac{t^a-1}a\ge\ln(t)$$

and assuming $a<0$,

$$\frac{t^a-1}a\le\ln(t)$$

Combining both cases gives us

$$\frac{1-t^{-a}}a\le\ln(t)\le\frac{t^a-1}a\quad\forall a>0$$