Как работать с асимптотическими наборами функций обозначений т.е. Биг-О + Биг-Омега?

Question

Я пытаюсь определить, является ли следующее утверждение истинным или ложным.

Если f (n) ∈ O (n) и g (n) ∈ Ω (n), то f (n) + g (n) ∈ Θ (n).

Мне кажется, я понимаю, добавляя ту же асимптотику big-O. O (n) + O (n) = O (n) Однако я не уверен в добавлении или работе с другими вместе взятыми.

Например: Если f (n) ∈ Θ (n log n), то f (n) * n =?

Может ли этот ответ быть одновременно O (n ^ 2 * logn) и Θ (n ^ 2 * logn)?

Заранее спасибо!

Answer 1

Вы можете использовать определение этих символов и попытаться найти доказательство или пример противоречия для них.

Если f(n) = O(n) и g(n) = Omega(n), то f(n) + g(n) не обязательно в Theta(n) обязательно!Как противоречие, если f(n) = n и g(n) = n^2, то f(n) + g(n) = Theta(n^2).С другой стороны, если f(n) = n и g(n) = n, то f(n) + g(n) = Theta(n).Следовательно, вы можете просто сказать f(n) + g(n) = Omega(n) и больше ничего.