By definition - $q(n)$ is a negligible function if for every positive integer $c>0$ there exist an integer $N_c$ such that for all $x>N_c$ :

  • $q(n)<1/x^c$

So for the function $1/x$, if we take the positive integer $c=1$ then we need to find some $N_c$ such that for every $x>N_c$:

  • $1/x<1/x$

$=>$ Definitely such $N_c$ does not exist then $1/x$ is not a negligible function.

Is that sufficient?

  • $\begingroup$ Why wouldn't it be? $\endgroup$
    – poncho
    Nov 22 '13 at 23:26
  • $\begingroup$ Related $\endgroup$
    – rath
    Nov 23 '13 at 0:01

Yes, that is sufficient.

I realise this isn't the most helpful of answers, but I'm not quite sure how we're supposed to deal with questions that lend themselves so neatly to one word answers. Certainly it seems wrong that something that has been solved should continue to sit in the 'unanswered questions' column!

  • $\begingroup$ I didn't know how to ask it differently.. $\endgroup$
    – Bush
    Nov 25 '13 at 19:27

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.