PUERTA | PUERTA CS 2012 | Pregunta 18

Deje que w(n) y A(n) denoten respectivamente, el peor caso y el tiempo promedio de ejecución de un algoritmo ejecutado en una entrada de tamaño n. ¿Cuál de las siguientes es SIEMPRE CIERTA?

(A) $A(n) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: La complejidad de tiempo del peor de los casos siempre es mayor o igual que la complejidad de tiempo del caso promedio.

El término escrito en notación Big O siempre puede ser asintóticamente igual o mayor que el término del otro lado.

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

Deja una respuesta Cancelar la respuesta