Нехтовна функція

Шаблон:Без джерелНехтовна функція (Шаблон:Lang-en) — функція $\mu (x):\mathbb{N}\to ℝ$ така, що для кожного додатнього цілого c існує ціле N_c таке, що для всіх x > N_c,

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

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

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

Приклади

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

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

$f(x)=\{\begin{array}{cc}\frac{1}{2^x},& xmod2\ne 0\\ \frac{1}{x^{1000}},& xmod2=0\end{array}$ — не нехтовна.