Análise de complexidade de tempo de 2 algoritmos arbitrários - provar ou refutar

Question

Dados 2 algoritmos A e B de tal modo que para cada tamanho de entrada, algoritmo A realiza metade do número de etapas algoritmo B executa no mesmo tamanho de entrada.

Denotamos a pior complexidade de tempo de cada um por $ g_a (n), g_b (n) $

Também sabemos que há uma função positiva $ f (n) $ tal que $ g_a (n) \ in\ Ômega (f (n)) $

É possível que $ g_b (n) \ in \ ômega (f (n)) $ ?É necessário?

Parece ingênuo pensar que é necessário, mas não consigo entender para contradizá-lo.

Answer 1

É possível. Exemplo $ g_a (n)= 1 $ , $ g_b (n)= 2 $ e classe="contêiner matemática"> $ f (n)= 1 $ .

Também é necessário, já que $ g_b (n)= 2 g_a (n) \ in \ ômega (f (n)) $ .

Para ver que $ 2 g_a (n) \ in \ ômega (F (n)) $ você pode usar a definição de $ \ ômega (\ Cdot) $ .

da $ g_a (n)=ômega (f (n)) $ você sabe que aqui é alguma $ n_0 $ e alguns $ c> 0 $ tal que, $ \ forall n \ GE n_0 $ , $ g_a (n) \ ge cf (n) $ . Isso implica que, para o mesmo valor da $ n_0 $ e $ c $ , $ 2 g_a (n) \ GE 2 cf (n) \ GE CF (n) $ , isto é, $ 2 g_a (n) \ in \ Ômega (F (n)) $ .