Solve an equation; big-O notation

Question

Suppose we have the following condition on the number of samples needed for an algorithm: $n \ge \frac{C}{\epsilon^2} \left[ \log \frac{1}{\delta} + D \log \frac{n}{D} \right]$. How can I give an estimate on how large $n$ needs to be in big-O notation? Important quantities are $\epsilon$ and $\delta$.

Answer 1

May be, you could consider the equation $$n=\frac{c }{\epsilon ^2}\left(d \log \left(\frac{n}{d}\right)-\log (\delta )\right)$$ which has a solution in terms of Lambert function $$n=-\frac{c\, d}{\epsilon ^2}\, W\left(-\frac{\epsilon ^2 }{c}\delta ^{\frac{1}{d}}\right)$$ Now, if $\epsilon$ is small, using $$W(x)=x-x^2+\frac{3 x^3}{2}-\frac{8 x^4}{3}+O\left(x^5\right)$$ you could get $$n=d \delta ^{\frac{1}{d}}+\frac{d \delta ^{2/d}}{c} \epsilon ^2+O\left(\epsilon ^4\right)$$