# Proving that a function is negligible

My question is about proving that a function is negligible if it is ran polynomial number of times.

This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'(n)$ is any polynomial. We multiply $p(n)$ both sides: $p(n)*negl_1(n) < p(n)/p'(n)$.

We let $p'(n)>>p(n)$. There is always a $p'(n)$ that satisfies this inequality. Thus, $negl_2(n) = p(n)*negl_1(n)$ is negligible.

Is my solution correct?

• You showed that there exists some polynomial function p', instead what you're looking for is to show that for any polynomial function p', then negl is smaller – Florian Bourse Apr 16 '18 at 9:11

Your solution is not correct. You have to show that $\mathbf{\text{negl}_2}$ satisfies the definition of negligible functions and what you "showed" actually is that given any sufficiently large polynomial $p'(n)$, it holds that $\mathbf{\text{negl}_2} < \frac{p(n)}{p'(n)}$.
• Try to prove it by contradiction supposing that $\mathbf{\text{negl}_2}$ is not negligible and then finding a polynomial whose inverse is asymptotically smaller than $\mathbf{\text{negl}_1}$.
• Try to prove it directly: from any given polynomial $p'(n)$, you know that $p(n)p'(n)$ is a polynomial, therefore, $\mathbf{\text{negl}_1}$ must be smaller than $1 / (p(n)p'(n))$ for all $n$ bigger than some $n_0$...