CGU-NET | UGC NET CS 2015 junio – III | Pregunta 35

Sean f(n) y g(n) funciones asintóticamente no negativas. ¿Cual de los siguientes es correcto?
(A) θ ( f (n)*g(n)) = mín (f (n), g(n))
(B) θ ( f (n)*g(n)) = máx (f (n) , g(n))
(C) θ( f (n) + g(n)) = min (f (n), g(n))
(D) θ ( f (n) + g(n)) = max (f (n), g (n))

Respuesta: (D)
Explicación:

• Caso-1:
  Cuando ninguna de las funciones f(n) y g(n) son funciones constantes – En este caso max(f(n) , g(n)) <= f(n) * g(n) así que max( f(n), g(n)) no puede proporcionar un límite superior para f(n) * g(n).
• Caso-2:
  Cuando tanto f(n) como g(n) son funciones constantes o cuando cualquiera de las funciones f(n) y g(n) es una función constante distinta de cero, en este caso f(n) * g(n) = theta(max(f(n), g(n))).
• Caso-3:
  Cuando al menos cualquiera de las f(n) y g(n) es 0, en este caso f(n) * g(n) != theta(max(f(n), g(n) )). Dado que max(f(n), g(n)) PODRÍA SER incapaz de dar un límite inferior.

La opción (D) es correcta.
Cuestionario de esta pregunta