Si $f(n)\in O(g(n))$ puede $g(n)\in O(f(n))$ ?

Question

Esto puede ser una pregunta tonta, pero si $f(n)\in O(g(n))$ puede $g(n)\in O(f(n))$ ? Se me ocurren algunos contraejemplos, como $n\in O(n^2)$ y obviamente $n^2\notin O(n)$ pero un contraejemplo no niega la existencia de un caso en el que sea cierto. ¿Es esto cierto o falso? ¿Y cómo puedo demostrarlo de cualquier manera?

¡Gracias!

Answer 1

Sí, es cierto. Decimos que $f(n)\in O(g(n))$ si existe una constante $C_1$ tal que $\lvert{f(n)}\rvert < C_1\lvert g(n) \rvert$ para un tamaño suficientemente grande $n$ , y de forma similar $g(n)\in O(f(n))$ si existe $C_2$ tal que $\lvert{g(n)}\rvert < C_2\lvert f(n)\rvert$ para un tamaño suficientemente grande $n$ . Ambas cosas son válidas si hay constantes $A$ y $B$ tal que $A\lvert g(n) \rvert < \lvert{f(n)}\rvert < B\lvert g(n) \rvert$ para un tamaño suficientemente grande $n$ o, por el contrario, que $$ A < \left\lvert{\frac{f(n)}{g(n)}}\right\rvert < B. $$ En este caso decimos que $f(n)\in\Theta(g(n))$ . La relación es simétrica y transitiva, y obviamente reflexiva, por lo que define una relación de equivalencia sobre el conjunto de funciones.