Ce nu sunt funcții care nu sunt neglijabile?

• Funcție neglijabilă: O functie $\mu$ este neglijabil dacă $\forall c \in N \;\; \există n_0 \în N$ astfel încât $\forall n \geq n_0, \mu(n) < n^{âc}.$

  Așa cum în general acum, o funcție neglijabilă este mai mică decât orice polinom. Avem și o definiție echivalentă a limitei;

  $f(n)$ este neglijabil decât pentru fiecare polinom $q(n)$ avem;

  $$\lim_{n \rightarrow \infty} q(n) f(n) =0$$

  Exemplele simple sunt cele $2^{-n},2^{-\sqrt{n}}, \text{ și } n^{- \log n}$.

• Funcție neneglijabilă:^* o functie $\mu(n)$ este neneglijabil dacă $\există c \în N$ astfel încât $\forall n_0 \în N, \există n \geq n_0$ astfel încât $\mu(n) \geq n^{-c}.$

  Pentru a fi deloc neglijabil, este suficient un singur candidat pentru a demonstra asta $n \geq n_0$ pentru care $\mu(n) \geq n^{-c}$.

• Funcție vizibilă: O functie $\mu$ este vizibil dacă $\există c \în N, n_0 \în N$ astfel încât $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

  După cum putem vedea, diferența față de non-neglijabilitate este; pentru toți $n \geq n_0$

  Un exemplu este $n^{-3}$ care este doar polinom lent (ca orice polinom)

  Funcțiile slabe unidirecționale sunt definite pe funcții vizibile.

Intercalarea este cheia pentru generarea de exemple distinctive. Luați orice funcție vizibilă și neglijabilă și intercalați-le;

$$\mu(n) = \case{ 2^{-n} & : $x$ este par \ n^{-3} & : $x$ este impar}$$

$\mu$ este o funcție deloc neglijabilă și neobservabilă!.

_{^*Negația cuantificatorilor: În negaţie $\neg\forall = \există$ și $\neg \exists = \forall$}