How to show a function is negligible?

1,133

You should exclude the trivial case of $p$ being a constant function. The precise statement is:

For every negligible function $\mu$ and for every nonconstant polynomial $p$ with positive leading coefficient, the composition $f = \mu\circ p$ is negligible. Indeed, for every $c>0$ we have $$|\mu(p(x))| < \frac{1}{p(x)^c} \tag{1}$$ whenever $p(x)$ is sufficiently large. Since $p$ has degree $\ge 1$ and positive leading coefficient, we have $p(x)>ax$ for some $a>0$ and for all sufficiently large $x$. Plug this into (1) to find $\mu\circ p$ is negligible.

For the second question: a function that decays faster than any polynomial will often have a decaying exponential term in it. Look for those. Formally, being negligible is equivalent to $$\lim_{x\to\infty} \frac{\log |f(x)|}{\log x} = -\infty$$

Share:
1,133

Related videos on Youtube

john carter
Author by

john carter

Updated on August 01, 2022

Comments

  • john carter
    john carter over 1 year

    Let $neg(x)$ be a negligible function (see here for the definition).
    Let p be a polynomial function such that $p(k)\geq 0$ for all $k>0$.

    What can we say about $f = neg(p(k))$? Is $f$ a negligible function? If yes, then is there any formal or informal way to check whether a given function is negligible?