# How to determine if a function is negligible?

In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems.

Although I know what is a negligible function, every time I encounter a function that need to be determined as negligible or not I just don't know how to do that. I just say that the function is negligible if it seems like $c/2^n$ where $c$ is a constant (or known to be negligible).

Can you provide an efficient method to determine quickly if a function is negligible or not?

• I'm not sure I fully understand your question, but maybe this tiny bit of algebra helps you: negligible functions are closed under addition (i.e. if $f, g$ are negligible, then so is the function $f + g$) and under multiplication with polynomials (i.e. if $f$ is negligible and $p$ is a polynomial then the function $n \mapsto f(n)⋅p(n)$ is negligible too). So if you encounter a function made up by addition of obviously negligible parts (e.g. $17^{−n}$), and multiplication with polynomials, you know that the result must also be negligible. Jan 3 '14 at 0:23
• How are you given the function? As a formula, as a black box, or as something else? Jan 3 '14 at 1:37
• The textbook by Katz and Lindell has a section on negligible functions and polynomials. Also, a quick web search gives some links that might help you, e.g.: cs.stackexchange.com/questions/11073/… Jan 3 '14 at 2:54