Is $k$ that satisfies $\alpha^{\frac{1}{k}}<1+ε$ polynomial in $\frac1ε$?

Question

I am doing an exercise in approximation algorithms course, and my algorithm takes as input a constant number $\alpha$ and finds the minimal $k_{0}$ s.t $\sqrt[k]{\alpha}<1+ε$ (this would promise me a $1+ε$ approximation).

Clearly, such $k_{0}$ exist and I am not bothered with calculating it within my algorithm. What I am bothered about is how my solution behaves as $ε\to0$.

My question is this: Is $k_{0}$, which is the minimal solution for $\sqrt[k]{\alpha}<1+ε$, polynomial in $\dfrac{1}{ε}$?

Answer 1

Since$$ α^{\frac{1}{k}} < 1 + ε \Longleftrightarrow \frac{1}{k} \ln α < \ln(1 + ε) \Longleftrightarrow k > \frac{\ln α}{\ln(1 + ε)}, $$ then$$ k_0 = \frac{\ln α}{\ln(1 + ε)} \sim \frac{\ln α}{ε} = \ln α · \frac{1}{ε}. \quad (ε \to 0^+) $$

Answer 2

Taking logarithms on both sides of your equations we have $$\ln(\alpha)\frac{1}{k}<\ln(1+\epsilon)$$ $$k>\frac{\ln(\alpha)}{\ln(1+\epsilon)}$$ As $\epsilon\to 0$, we can expand $\ln(1+\epsilon)$ using it's taylor expansion as $\ln(1+\epsilon)=\epsilon-\frac{\epsilon^2}{2}+\frac{\epsilon^3}{3}-...\approx \epsilon-\frac{\epsilon^2}{2}$ upto second order in $\epsilon$. Thus, $$k>\frac{\ln(\alpha)}{\epsilon-\frac{\epsilon^2}{2}}=\frac{\ln(\alpha)}{\epsilon(1-\frac{\epsilon}{2})}$$ Now, for small epsilon, we also have $(1-\epsilon/2)^{-1} \approx 1+\epsilon/2$. Thus, $$k>\frac{\ln(\alpha)}{\epsilon}(1+\frac{\epsilon}{2})$$

Answer 3

A cruder but simpler estimate:

$\sqrt[k]{\alpha}<1+\epsilon$ is the same as $\alpha < (1+\epsilon)^k$.

Since, by good old Bernoulli, $(1+\epsilon)^k \gt 1+k\epsilon$, if $\alpha < 1+k\epsilon$ then $k$ is acceptable.

Therefore $k > \dfrac{\alpha-1}{\epsilon}$ will work.

Of course, this is not as good as the bound $\dfrac{\ln(\alpha)}{\epsilon}$.