2
$\begingroup$

I am having a hard time understanding and applying the formulas that are used to identify a function is negligible or not?

  • One text defines it as; a function $f$ from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial $p$ there is an $N$ such that for all integers $n > N$ it holds that $f(n) < 1/p(n)$.
  • Another textbook defines it as; a function $f$ is negligible if, for every polynomial $p$, we have $\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda)=0$

Example: $1/2^{\lambda/2}$ would this be considered as negligible function?

$\endgroup$
  • $\begingroup$ The two definitions are equal. Try to find a function which fulfills one and not the other, that should result in a contradiction. Exponential functions are the most obvious example of negligible or super-polynomial functions (depending on the base), but they are not the only ones. $\endgroup$ – tylo Dec 21 '18 at 20:19
1
$\begingroup$

Let me first recall the definition and some properties of the exponential function. The exponential function in basis $a$ is defined as follows: $ \exp_a(x) = a^x$. If $a>1$, such a function grows faster than any polynomial $p(x)$. More formally, this property is interpreted in the two following ways.

  • 1) For any polynomial $p$ and any basis $a>1$, there exists $N$ such that for all $n\geq N, \exp_a(n) > p(n)$.

  • 2) For any polynomial $p$ and any basis $a>1$, $\lim_\limits{x \rightarrow \infty} \frac{\exp_a(x)}{p(x)} = \infty $ (and so $\lim_\limits{x \rightarrow \infty} \frac{p(x)}{\exp_a(x)} = 0 $)

Now, we remark that the function $h(\lambda) = 2^{\lambda/2}$ is an exponential function, because $h(\lambda) = 2^{\lambda/2}=\left(2^{1/2}\right)^\lambda= \sqrt{2}^\lambda =\exp_{\sqrt{2}}(\lambda)$. Finally, your function is $f(\lambda) = \frac{1}{\exp_{\sqrt{2}}(\lambda)}$. In the following, we will prove that $f$ is negligible using the two definitions.

  • 1) $\sqrt{2} >1$, so for any polynomial $p$, there exists $N$ such that for all $n\geq N, \exp_\sqrt{2}(n) > p(n)$, which implies that for all $n\geq N, \frac{1}{\exp_\sqrt{2}(n)} < \frac{1}{p(n)}$. Since $f(\lambda) = \frac{1}{\exp_{\sqrt{2}}(\lambda)}$, we deduce that for all $n\geq N, f(n) < \frac{1}{p(n)}$.

  • 2) $\sqrt{2} >1$, so for any polynomial $p$, $\lim_\limits{\lambda \rightarrow \infty} \frac{p(\lambda)}{\exp_\sqrt{2}(\lambda)} = 0 $. Since $\frac{p(\lambda)}{\exp_\sqrt{2}(\lambda)} = p(x) \frac{1}{\exp_\sqrt{2}(\lambda)} = p(\lambda) f(\lambda)$, we deduce that $\lim_\limits{\lambda \rightarrow \infty} p(\lambda) f(\lambda) = 0 $

To conclude, the intuition is that a polynomial divide by something that grows faster than any polynomial is a negligible function, because it becomes very small very quickly.

$\endgroup$
  • $\begingroup$ Actually there is a large range of functions, which are in between all polynomials and the exponential function. If you replace the exp function with a general super-polynomial function, this answer would be more accurate. $\endgroup$ – tylo Dec 21 '18 at 20:14
1
$\begingroup$

From the first definition;

To see that a function is negligible, you have to find an $n >N$ for every positive polynomial $p(n)$ such that after $f(n) < 1/p(n)$ is holds. Here two examples;

  • consider $p(n)= 10^6$ then $n \geq 800$ then $1/2^{800/2} = 1/1048576 < 1/10^{-6}$
  • consider $p(n)= 10^{3}$ then $n \geq 200$ then $1/2^{200/2} = 1/1024 < 1/10^{-3}$

From the second definition; $\lim_{\lambda \rightarrow \infty} p(\lambda) f(\lambda) =0?$

For your $f(\lambda) = 1/2^{\lambda/2}$ we have to see that the limit is 0 whatever the polynomial $p(\lambda) = a_n \lambda^n +\ldots + a_0$

$$\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda) = \frac{p(\lambda)}{2^{\lambda /2 }} = \lim_{\lambda \rightarrow \infty} \frac{a_n \lambda^n +\ldots + a_0}{2^{\lambda /2 }} = 0,$$

since if you take the L'Hôpital's rule the $n$-times the numerator will be 1 and eventually zero. The denumerator, however, goes to infinity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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