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) &lt; 1/p'(n)$ where $p'(n)$ is any polynomial. We multiply $p(n)$ both sides: $p(n)*negl_1(n) &lt; p(n)/p'(n)$.

We let $p'(n)&gt;&gt;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?
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} &lt; \frac{p(n)}{p'(n)}$.

I see two easy ways of solving that exercise:


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$...