convertir la asintótica little-oh en big-oh

Question

Sea $f(n)$ sea una función aleatoria tal que $f(n)\cdot n^{1/4-\epsilon}\to 0$ para todos $\epsilon>0$ . Digamos que sabemos que $f(n)\cdot n^{1/4}\not\to 0$ . ¿Implica esto que $f(n)=\tilde O(n^{-1/4})$ ?

(donde el $\tilde{O}$ significa hasta factores logarítmicos).

Answer 1

Si $f(n)\cdot n^{1/4 - \varepsilon}\rightarrow 0$ entonces $f(n) \in o(n^{\varepsilon-1/4}) \subseteq O(n^{\varepsilon-1/4})$ . Si esto es cierto para todos $\varepsilon > 0$ entonces $$ f(n) \in \bigcap_{\varepsilon > 0} o(n^{\varepsilon - 1/4}). $$ Además, si $f(n)\cdot n^{1/4}\not\rightarrow 0,$ entonces $f(n)\not\in o(n^{-1/4})$ aunque podría estar en la clase más grande $O(n^{-1/4})$ . Para que sepas exactamente esto: $$ f(n)\in \bigcap_{\varepsilon > 0} o(n^{\varepsilon - 1/4}) \setminus o(n^{-1/4}). $$ Otra forma de decirlo es que $f(n)=n^{-1/4}g(n)$ donde $g(n)$ crece más lentamente que cualquier polinomio, pero no converge a cero. Tu pregunta (corregida) es, ¿implica esto que $$ f(n) \in \tilde{O}(n^{-1/4})=\bigcup_{k}O(n^{-1/4}\log^k n )\; ? $$ En otras palabras, ¿es necesario que $g(n)$ crece más lentamente que alguna potencia de $\log n$ ? En sentido estricto, la respuesta es no. Hay funciones que crecen más lentamente que cualquier polinomio pero más rápidamente que cualquier potencia del logaritmo; p. ej, $g(n)=\exp(\sqrt{\log n})$ . Si $f(n) = n^{-1/4} g(n)$ para alguna función de este tipo, entonces puede encajar entre lo que sabes y lo que te gustaría afirmar.