Join Log in
Score:1
MR.-c avatar Crypto

Proving negligible function

in flag
MR.-c

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?

95
0 + 0
Score:2
avatar Crypto
cn flag
Maeher
  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.
0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.