Algoritmos | Análisis de Algoritmos | Pregunta 13

Considere las siguientes funciones:

  f(n)   = 2^n
  g(n)   = n!
  h(n)   = n^logn 

¿Cuál de las siguientes afirmaciones sobre el comportamiento asintótico de f(n), g(n) y h(n) es verdadera?
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = (g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = (f(n))
(A) A
(B) B
(C) C
(D) D

Respuesta: (D)
Explicación: Según el orden de crecimiento: h(n) < f(n) < g(n) (g(n) es asintóticamente mayor que f(n) y f(n) es asintóticamente mayor que h(n) )
Podemos ver fácilmente el orden anterior tomando registros de las 3 funciones dadas

   lognlogn < n < log(n!)  (logs of the given f(n), g(n) and h(n)).

Tenga en cuenta que log(n!) = (nlogn)
Cuestionario de esta pregunta