Доказательство замыкания асимптотически ограниченных функций при сложении

Question

Я хотел бы доказать это утверждение:

Если f (n) - тета (h (n)) и g (n) = O ((h (n)), то f (n) + g (n) равно O (h (n)).

Предполагается, что все функции неотрицательные и монотонно неубывающие.

Мои попытки доказательства объясняют, что если f (n) и g (n) являются O (h (n)), тогда существует:

положительных постоянных n0, c0, таких что f (n) <= c0 * h (n) для всех n> = n0

положительных постоянных n1, c1, таких что f (n) <= c1 * h (n) для всех n> = n1

Следовательно, можно сделать вывод, что g (n) + f (n) <= (c1 + c0) * h (n) для всех n> = max (n1, n0), что означает, что g (n) + f (n) равно O (h (n))

Это правильно? Есть ли более строгие доказательства ... например, от противного?

Answer 1

Ваше доказательство правильное и строгое. Это прямое и конструктивное доказательство того, что вы не только показываете, что подходящие c и n0 существуют, но вы говорите, как рассчитать их из предположений. Никаких других более простых способов доказательства здесь не приходит на ум.