Negligible function

In mathematics, a negligible function is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> 
 
 
 
 μ
 :
 
 N
 
 →
 
 R
 
 
 
 {\displaystyle \mu :\mathbb {N} \to \mathbb {R} }
 
 such that for every positive integer c there exists an integer Nc such that for all x > Nc,

|
 
 μ
 (
 x
 )
 
 |
 
 <
 
 
 1
 
 x
 
 c
 
 
 
 
 .
 
 
 {\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}

Equivalently, the following definition may be used.
A function 
 
 
 
 μ
 :
 
 N
 
 →
 
 R
 
 
 
 {\displaystyle \mu :\mathbb {N} \to \mathbb {R} }
 
 is negligible, if for every <a href="/facts/Positive_polynomial/WIl2Mv9s">positive polynomial</a> poly(·) there exists an integer Npoly > 0 such that for all x > Npoly

|
 
 μ
 (
 x
 )
 
 |
 
 <
 
 
 1
 
 poly
 ⁡
 (
 x
 )
 
 
 
 .
 
 
 {\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}

Negligible function open-in-new

Negligible function