$(1 - \frac{\epsilon}{2})^k = \epsilon$, solve for $k$ I am currently reading a paper which states that if $k = O(\frac{1}{\epsilon}\log{\frac{1}{\epsilon}})$, then $(1 - \frac{\epsilon}{2})^k = \epsilon$. However, I am unable to get the algebra to work out. Using logarithm rules, I get that $k = \frac{\log{\epsilon}}{\log({1 - \frac{\epsilon}{2}})}$, but am unsure of where to go from here. What are the steps required to achieve the desired result?

I presume that what was meant by $\displaystyle k = O\left(\tfrac 1 \varepsilon \log\tfrac 1 \varepsilon \right)$ is $\displaystyle k = O\left(\tfrac 1 \varepsilon \log\tfrac 1 \varepsilon \right) \text{ as } \varepsilon\downarrow 0.$
If you have $k = \dfrac{\log\varepsilon}{\log\left(1 - \frac \varepsilon 2 \right)}$ you can first say that $\log\left( 1 - \frac \varepsilon 2 \right) \approx -\frac\varepsilon 2,$ since that's just using the tangent line to the logarithm function at $1$ as an approximation to the curve.
$$
\frac{\log \varepsilon}{\log\left(1- \frac \varepsilon 2 \right)} \approx -\frac 2 \varepsilon \log\varepsilon = \frac 2 \varepsilon \log\frac 1 \varepsilon.
$$
