# Negligible function arithmetics

By definition of negligible function, if $q(n)$ is a negligible function, does $poly(n)*q(n)$ is also a negligible function? How can I prove it?

• What's "poly(n)" ? Any polynomial with integer (natural) coefficients evaluated at $\;n\;$ ? – DonAntonio Nov 23 '13 at 22:16
• @DonAntonio: yes, the wikipedia article that OP links to uses that term. – Ross Millikan Nov 23 '13 at 22:34

Yes, it is also a negligible function. First you have to find a power of $n$ that is eventually greater than $poly(n)$. You can do this, just take a power higher than the highest power in $poly(n)$ Let it be $n^k$ and $n^k \gt poly(n)$ whenever $n \gt N_1$
Now if somebody gives us a $c$, we have to find an $N_c$ such that $poly(n)q(n) \lt \frac 1{n^c}$ whenever $n \gt N_c$. Because $q(n)$ is negligible, we can find an $N_q$ such that $q(n) \lt \frac 1{n^{c+k}}$. Then we can take $N_c=\max (N_1,N_q)$ and $poly(n)q(n)\lt n^kq(n) \lt n^k\frac 1{n^{c+k}}=\frac 1{x^c}$
• Is this also holds that non-negligible function multiply by some $poly(n)$ is also a non-negligible function? – Bush Nov 24 '13 at 20:25