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}&lt;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}&lt;1+ε$, polynomial in $\dfrac{1}{ε}$?
Since$$
α^{\frac{1}{k}} &lt; 1 + ε \Longleftrightarrow \frac{1}{k} \ln α &lt; \ln(1 + ε) \Longleftrightarrow k &gt; \frac{\ln α}{\ln(1 + ε)},
$$
then$$
k_0 = \frac{\ln α}{\ln(1 + ε)} \sim \frac{\ln α}{ε} = \ln α · \frac{1}{ε}. \quad (ε \to 0^+)
$$
Taking logarithms on both sides of your equations we have
$$\ln(\alpha)\frac{1}{k}&lt;\ln(1+\epsilon)$$
$$k&gt;\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&gt;\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&gt;\frac{\ln(\alpha)}{\epsilon}(1+\frac{\epsilon}{2})$$