Pequeña notación oh

Question

La función GNFS $f(n)$ con $n$ el número para el que buscamos la factorización muestra la complejidad de dicha factorización:

\begin{align} f(n) = e^{\left(\sqrt[3]{\frac{64}{9}} + o(1)\right)\left(\ln n\right)^{\frac{1}{3}} \left(\ln\ln n\right)^{\frac{2}{3}}} \end{align}

¿Cuál es el significado y el valor de $o(1)$ ?

Gracias por la ayuda.

Answer 1

Significa, por definición : "que va a $0$ como $n\to\infty$ ."

Ahora, para el valor... podría ser cualquier función convergente a $0$ . En este caso concreto, se podría intentar obtener más información sobre este término de orden inferior, pero sin más información no podemos decir nada más.

Answer 2

Dadas dos funciones $h, g \colon \mathbb{N} \to \mathbb{N}$ en general $h \in o(g)$ significa que para cada elección de una constante $k > 0$ se puede encontrar una constante $a$ tal que la desigualdad $0 \leq h(n) < k \, g(n)$ es válido para $n > a$ .

Toma, $1$ representa la función constante $g(n) = 1$ para todos $n \in \mathbb{N}$ . Por lo tanto, $o(1)$ en su expresión representa cualquier función $h \colon \mathbb{N} \to \mathbb{N}$ tal que, para cada elección de una constante $k > 0$ existe una constante $a$ tal que $0 \leq h(n) < k$ es válido para $n > a$ . En otras palabras, $\lim_{n \to \infty} h(n) = 0$ .