0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Is this also holds that non-negligible function multiply by some $poly(n)$ is also a non-negligible function? $\endgroup$ – Bush Nov 24 '13 at 20:25
  • $\begingroup$ Yes, that is correct. As all polys go to infinity, they can't make something negligible $\endgroup$ – Ross Millikan Nov 24 '13 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.