Показывает f(n) = O(f(n) + g(n))?

Question

Мне было интересно, что доказательство для следующего сравнения Big-O:

f (n) является O(f(n) + g(n)))

Я понимаю, что мы могли бы использовать:

f (n) ≤ константа * (f(n) + g(n))

Но я не знаю, как это сделать.

Как насчет случая, когда мы заменяем big-O на big-Ω?

Answer 1

Если вы знаете, что функция g (n) неотрицательна, то обратите внимание, что

f(n) ≤ f(n) + g(n) = 1 · (f(n) + g(n))

Учитывая это, не могли бы вы использовать формальное определение нотации big-O, чтобы показать, что f(n) = O(f(n) + g(n))?

Если g (n) не обязательно неотрицателен, то этот результат не обязательно верен. Например, возьмем f (n) = n и g(n) = -n. Тогда f(n) + g(n) = 0, и неверно, что f(n) = O(0).

Что касается случая Ω, вы уверены, что этот результат обязательно верный? В качестве подсказки попробуйте выбрать f (n) = n и g (n) = 2ⁿ. Действительно ли f (n) Ω(f(n) + g(n)) здесь?

Надеюсь это поможет!