L'analisi della complessità del tempo di 2 algoritmi arbitrari - dimostra o confutare

Question

Ci sono dati 2 algoritmi A e B in modo tale che per ogni dimensione di ingresso, l'algoritmo A esegue metà del numero di passaggi l'algoritmo B esegue sulla stessa dimensione di ingresso.

Dendiamo la peggiore complessità del tempo di ciascuno di $ G_A (N), G_B (n) $

Inoltre, sappiamo che c'è una funzione positiva $ f (n) $ tale che $ g_a (n) \ in\ Omega (f (n)) $

È possibile che $ G_B (n) \ in \ omega (f (n)) $ ?È necessario?

Sembra ingenuo pensare che sia necessario, ma non riesco a capire di contraderlo.

Answer 1

è possibile. Esempio $ G_A (n)= 1 $ , $ G_B (n)= 2 $ e $ f (n)= 1 $ .

È anche necessario, poiché $ G_B (n)= 2 G_A (n) \ in \ omega (f (n)) $ .

per vedere quella $ 2 g_a (n) \ in \ omega (f (n)) $ È possibile utilizzare la definizione di $ \ omega (\ cdot) $ .

da $ g_a (n)=omega (f (f (f (f (f (f (f (f (n)) $ sai che ecco alcuni $ n_0 $ e alcuni $ c> 0 $ tale che, $ \ forall n \ ge n_0 $ , $ G_A (n) \ Ge CF (n) $ . Ciò implica che, per lo stesso valore di $ n_0 $ e $ c $ , $ 2 G_A (n) \ Ge 2 cf (n) \ ge cf (n) $ , cioè, $ 2 g_a (n) \ in \ Omega (f (n)) $ .