Відкрити головне меню

Нехтовна функція (англ. negligible function) — функція така, що для кожного додатнього цілого c існує ціле Nc таке, що для всіх x > Nc,

Тотожно, ми можемо використовувати таке визначення: Функція є нехтовною, якщо для кожного додатнього багаточлену poly(·) існує ціле Npoly > 0 такий, що для всіх x > Npoly

ПрикладиРедагувати

  — нехтовна,
  — не нехтовна, бо якщо покласти с = 10 000, тоді  
  — не нехтовна.