Is $k$ that satisfies $\alpha^{\frac{1}{k}}<1+ε$ polynomial in $\frac1ε$? 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}{ε}$?
 A: 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^+)
$$
A: 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}$.
A: 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})$$
