# Identifying negligible functions

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?

• 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. – tylo Dec 21 '18 at 20:19

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.

• 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. – tylo Dec 21 '18 at 20:14

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.