I try to found Lower bound on $k$ when $(1-\varepsilon )^k < \frac{3}{4n}$. The lower bound should be $k=\Omega(\log{n})$ but I can't find a way to prove that... I tried to use Bernoulli's inequality but the result was not good enough I also tried to proved using combinatorics methods but that also failed. Anyone got an idea?


Edit: $\varepsilon$ is constant s.t. $0<\varepsilon<1$

  • 3
    $\begingroup$ Presumably $ 0 < \epsilon < 1$? In which case taking logarithms gives you $k \log (1-\epsilon) < - \log 4n/3,$ and dividing by $\log (1- \epsilon),$ which is negative, gives you $k > \frac{\log 4n/3}{ - \log (1-\epsilon)},$ which is of the required form as long as $\epsilon$ is bounded away from $0$ independently of $n$. $\endgroup$ Commented Mar 29, 2018 at 11:59
  • $\begingroup$ Thanks, it is indeed solve my question. $\endgroup$
    – ron653
    Commented Mar 29, 2018 at 12:04


You must log in to answer this question.

Browse other questions tagged .