Análisis de complejidad de tiempo de 2 algoritmos arbitrarios: pruebe o refrescan

Question

Se nos proporcionan 2 algoritmos A y B de los que para cada tamaño de entrada, el algoritmo A realiza la mitad del número de pasos del algoritmo B realiza en el mismo tamaño de entrada.

Denotamos la peor complejidad de cada uno de cada uno por $ g_a (n), g_b (n) $

También sabemos que hay una función positiva $ f (n) $ tal que $ g_a (n) \ en\ Omega (f (n)) $

es posible que $ g_b (n) \ in \ omega (f (n)) $ ?¿Es necesario?

Parece ingenuo pensar que es necesario, pero no puedo descubrir que lo contradice.

Answer 1

es posible. Ejemplo $ g_a (n)= 1 $ , $ g_b (n)= 2 $ , y $ f (n)= 1 $ .

También es necesario, ya que $ g_b (n)= 2 g_a (n) \ in \ omega (F (n)) $ .

para ver que $ 2 g_a (n) \ in \ omega (f (n)) $ Puede usar la definición de $ \ \ omega (\ cdot) $ .

de $ g_a (n)=onga (f (n)) $ Usted sabe que aquí está un poco $ n_0 $ y algunos $ c> 0 $ tal que, $ \ forall n \ ge n_0 $ , $ g_a (n) \ ge cf (n) $ . Esto implica que, por el mismo valor de $ n_0 $ y $ C $ , $ 2 G_A (N) \ GE 2 CF (N) \ GE CF (N) $ , es decir, $ 2 g_a (n) \ in \ Omega (f (n)) $ .