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, 2013 at 23:26
  • $\begingroup$ Related $\endgroup$
    – rath
    Nov 23, 2013 at 0:01

1 Answer 1


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, 2013 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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