О (f (n)) + Ω (g (n)) равно Ω (f (n)) + O (g (n))?

Question

Верно ли следующее уравнение? :

O (f (n)) + Ω (g (n)) = Ω (f (n)) + O (g (n))

Я знаю, что Big O означает не лучше чем (функция), а Big Omega означает не хуже чем (функция). Но я не знаю, делает ли это приведенное выше утверждение истинным или ложным.

Answer 1

Пусть $ f (n) = n, g (n) = 2 ^ n $

$ t (n) = 2n $ входит во второй набор, потому что $ n = Ω (f (n) ) $ и $ n = O (g (n)) $, но не в первом

Answer 2

У нас есть три общих случая (для возрастающих функций):

• Случай 1: f (n) ∈ o (g (n)) (обратите внимание на "маленький-ой").

  В этом случае O (f (n)) ⊂ O (g (n)) и Ω (g (n)) ⊂ Ω (f (n)). Следовательно, O (f (n)) + Ω (g (n)) является собственным подмножеством O (g (n)) + Ω (f (n)).

  Например, если f ( n) = n и g (n) = n ³ , тогда n ² находится в Ω (f (n)) + O (g (n)), но это не так в O (f (n)) + Ω (g (n)).

• Случай 2: f (n) ∈ Θ (g (n))

  В этом случае O (f (n)) = O (g (n)) и Ω (g (n)) = Ω (g (n)), поэтому два набора равны.

• Случай 3: f (n) ∈ ω (g (n))

  Этот случай эквивалентен случаю 1, только с f и g перевернуто. Таким образом, по симметрии мы имеем, что O (f (n)) + Ω (g (n)) является правильным надмножеством O (g (n)) + Ω (f (n)).

В сумме эти два набора в общем не равны.