I was reading the following:

The functions $2^{-n}, 2^{-\sqrt{n}}$ are negligible. However they approach zero at different rates. For example, we can look at the minimum value of $n$ for which each function is smaller than $\frac{1}{n^5}$

  1. Solving $2^{-n} < n^{-5}$ we get $n>5\cdot log(n)$. The smallest integer value of $n>1$ for which this holds is $n=23$.

1- I don't understand why/how did they choose $1/n^5$ and not other function for comparison.

2- How to solve the inequality to be $n>5\cdot log(n)$ ?

3- How to find that the smallest integer is 23 without trying/guessing the numbers?


1 Answer 1

  1. It's a more or less arbitrary example to illustrate a point.
  2. \begin{align}&2^{-n} <n^{-5}\\ \iff &\log_22^{-n} < \log_2n^{-5}\tag{take $\log_2$}\\ \iff &-n < -5\cdot \log_2n\tag{use log rules}\\ \iff &n > 5\cdot \log_2n\tag{multiply by $-1$}\end{align}
  3. It's a small number, so trying numbers starting at 2 should do the trick. You're checking that $\frac{n}{\log n} \leq 5$ and that function is monotone, so you could also do a binary search over an appropriate interval.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.