Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2013)

Нехтовна функція (англ. negligible function) — функція ${\displaystyle \mu (x):\mathbb {N} {\rightarrow }\mathbb {R} }$ така, що для кожного додатнього цілого c існує ціле N_c таке, що для всіх x > N_c,

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

Тотожно, ми можемо використовувати таке визначення: Функція ${\displaystyle \mu (x):\mathbb {N} {\rightarrow }\mathbb {R} }$ є нехтовною, якщо для кожного додатнього багаточлену poly(·) існує ціле N_poly > 0 такий, що для всіх x > N_poly

${\displaystyle |\mu (x)|<{\frac {1}{{\text{poly}}(x)}}.}$

${\displaystyle |\mu (x)|<{\frac {1}{2^{x}}}}$ — нехтовна,

${\displaystyle |\mu (x)|<{\frac {1}{x^{1000}}}}$ — не нехтовна, бо якщо покласти с = 10 000, тоді ${\displaystyle {\frac {1}{x^{1000}}}>{\frac {1}{x^{c}}},}$

${\displaystyle f(x)={\begin{cases}{\frac {1}{2^{x}}},&x\mod 2\neq 0\\{\frac {1}{x^{1000}}},&x\mod 2=0\end{cases}}}$ — не нехтовна.

На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій.