Identifying negligible functions

Question

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?

Answer 1

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.

Answer 2

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.