Big Oh, petites relations Oh et Big thêta

Question

Si une fonction f (x) = O (g (x)), alors il y a une chance que f (x) = Ω (g (x)) et f (x) = Θ (g (x)), mais si f (x) = o (g (x)), est-il possible que f (x) = Ω (g (x)), ou f (x) = ω (g (x))?

Answer 1

Nous donnons quelques définitions formelles:

f(n) = o(g(n)) 
<=> forall c > 0 exists k > 0 s.t. 0 <= f(n) < cg(n) forall n >= k. 
<=> g(n) = ω(f(n)) 

f(n) = O(g(n)) 
<=> exists c > 0 exists k > 0 s.t. 0 <= f(n) < cg(n) forall n >= k. 
<=> g(n) = Ω(f(n)) 

f(n) = ϴ(g(n)) 
<=> f(n) = O(g(n)) and g(n) = O(f(n)) 

On suppose f(n) = o(g(n)). Question 1: peut f(n) = Ω(g(n))? Si oui, alors il doit exister c, k tel que pour tous n >= k, 0 <= g(n) < cf(n). De l'hypothèse nous savons que pour tous c' il existe certains k' tel que pour tous n >= k', 0 <= f(n) < cg(n). Laisser k'' = max(k, k'). Nous devons avoir:

0 <= g(k'') < cf(k'') 
0 <= f(k'') < c'g(k'') 
=> 0 <= g(k'') < cc'g(k'') 

Cela doit tenir pour tout choix de c' > 0. Tout ce que nous savons sur c est que celui-là existe; mais tant que f(n) et g(n) sont strictement supérieures à zéro, nous savons qu'il doit y avoir un plus petit c qui fonctionne. Soit c'' être le plus petit choix valide de c à k''. Ensuite, nous pouvons choisir c' = 1/c''. Par conséquent nous aurions besoin

0 < g(k'') < g(k'') 

Ce qui est toujours faux. Par conséquent, tant que f(n) et g(n) ne sont pas (finalement) égal à zéro, nous ne pouvons pas avoir simultanément f(n) = o(g(n)) et f(n) = Ω(g(n)). Puisque f(n) = ω(g(n)) implique f(n) = Ω(g(n)), et nous savons que ce dernier n'est pas vrai à la lumière de notre hypothèse, nous pouvons également répondre à la question 2 en toute sécurité.