Big Oh, kleine Oh und Big Theta Relationen

Question

Wenn eine Funktion f (x) = O (g (x)) ist, dann besteht die Möglichkeit, dass f (x) = Ω (g (x)) und f (x) = Θ (g (x)), aber wenn f (x) = o (g (x)), ist es möglich, dass f (x) = Ω (g (x)) oder f (x) = ω (g (x))?

Answer 1

Wir geben einige formale Definitionen:

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)) 

f(n) = o(g(n)) Angenommen. Frage 1: kann f(n) = Ω(g(n))? Wenn ja, dann muss c, k so existieren, dass für alle n >= k, 0 <= g(n) < cf(n). Aus der Annahme heraus, dass für alle c' gibt es einige so dass für alle n >= k', 0 <= f(n) < cg(n). Lassen Sie k'' = max(k, k'). Wir müssen:

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

Dies ist für jede Wahl von c' > 0 halten müssen. Alles, was wir über c wissen ist, dass man existiert; aber solange f(n) und g(n) streng größer als Null sind, wissen wir, dass es eine kleinste c geben muss, die funktioniert. Lassen Sie c'' die kleinste gültige Wahl von c bei k'' sein. Dann können wir wählen c' = 1/c''. Deshalb würden wir benötigen

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

Das ist immer falsch. Solange also f(n) und g(n) nicht (schließlich) gleich Null sind, können wir f(n) = o(g(n)) und f(n) = Ω(g(n)) nicht gleichzeitig haben.

Da f(n) = ω(g(n))f(n) = Ω(g(n)) bedeutet, und wir wissen, dass Letzteres im Lichte unserer Annahme nicht wahr ist, können wir auch Frage 2 negativ beantworten.