¿Si $f(n)$ $O(g(n))$ y $g(n)$ $O(f(n))$, es $f(n) = g(n)$?

Question

¿Pregunta: si $f(n)$ $O(g(n))$ y $g(n)$ $O(f(n))$, es $f(n) = g(n)$?

Estoy estudiando para una prueba de matemática discreta, y no estoy seguro si esto es verdadero o falso. ¿Desde Big-OH ignora múltiplos constantes, no $f(n) = c\, g(n)$?

Answer 1

Tus pensamientos son correctos. Considerar $f(n) = n$ y $g(n) = 2f(n)$ como un ejemplo contrario.

Answer 2

Considerar $f(n) = an^2$ y $g(n) = bn^2$ donde $a$ y $b$ son reales positivos distintos.

Ambos % son verdaderas, $f(n) = O(g(n))$y $g(n) = O(f(n))$ $f(n) \ne g(n)$ $n > 0$.

Esto se escribe a menudo como $f(n) = \Theta(g(n))$.