Sean f(n) = n 2 Logn y g(n) = n (logn) 10 dos funciones positivas de n. ¿Cuál de las siguientes afirmaciones es correcta?
(A) f(n) = O(g(n)) y g(n) != O(f(n))
(B) f(n) != O(g(n)) y g(n) = O(f(n))
(C) f(n) = O(g(n)) pero g(n) = O(f(n))
(D) f(n) != O(g(n) )) pero g(n) != O(f(n))
Respuesta: (B)
Explicación:
Cualquier potencia constante de Logn es asintóticamente menor que n.
Prueba:
Dado f(n) =n 2 Logn y g(n) = n (logn) 10
En este tipo de preguntas, le sugerimos que primero cancele el factor común en ambas funciones. Después de eliminar estos, nos quedamos con f(n) = n y g(n) = (logn) 9 . Eliminando un factor de nlogn de ambas funciones.
Ahora, n es asintóticamente muy, muy grande en comparación con cualquier potencia integral constante de (logn) que podemos verificar sustituyendo un valor muy grande, digamos 2 100 .
f(2 100 ) = 2 100 = 1030 y g(2 100 ) = 100 9 = 1018.
Recuerde siempre sustituir valores muy grandes de n para comparar ambas funciones. De lo contrario, llegará a conclusiones erróneas porque si f(n) es asintóticamente mayor que g(n), eso significa que después de un valor particular de n, f(n) siempre será mayor que g(n).
Esta solución es aportada por Pranjul Ahuja .
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA