Algoritmos | Análisis de Algoritmos | Pregunta 15

Considere las siguientes funciones

¿Cuál de las siguientes es verdadera? (GATE CS 2000)
(a) h(n) es 0(f(n))
(b) h(n) es 0(g(n))
(c) g(n) no es 0(f(n) )
(d) f(n) es 0(g(n))
(A) a
(B) b
(C) c
(D) d

Respuesta: (D)
Explicación: g(n) = 2^ = n^

f(n) y g(n) son del mismo orden asintótico y las siguientes declaraciones son verdaderas.
f(n) = O(g(n))
g(n) = O(f(n)).

(a) y (b) son falsas porque n! es de orden asintóticamente mayor que n^ .
Cuestionario de esta pregunta