Докажите, что f (n) + d (n) = O (g (n) + h (n))

Если f(n) is Ο(g(n)) и d(n) is Ο(h(n)), докажите, что f(n) + d(n)= O(g(n)+ h(n))

У меня проблемы с официальным доказательством.

Вот что у меня есть на данный момент:

f(n)=O(g(n)) and d(n)=O(h(n)) so, O(g(n)) + O(h(n)) = O(g(n)+ h(n))

Но я не уверен в этом, потому что это кажется очень простым.

Любая помощь приветствуется.

РЕДАКТИРОВАТЬ: я должен это доказать, я не могу доказать это, сказав пример, я должен решить это как доказательство, используя константу C, я думаю, или каким-то другим способом ..


analysis algorithm big-o notation
person Community    schedule 22.04.2018    source источник
comment
stackoverflow.com/questions/12946600/sum-of-big -о-обозначение   -  person Ctznkane525    schedule 23.04.2018
comment
stackoverflow.com/questions/7007723 /   -  person Ctznkane525    schedule 23.04.2018
comment
Возможный дубликат Большой O при сложении разных подпрограмм   -  person Ctznkane525    schedule 23.04.2018
comment
да, но я думаю, что эти ссылки не дают ответа на мой вопрос   -  person    schedule 23.04.2018
comment
Доказательство начнется с утверждения, что означает, что f (n) будет O (g (n)) и d (n) будет O (h (n)), используя определение большого O. Чтобы продолжить, рассмотрим, что определение требует, чтобы оно было истинным, чтобы f (n) + d (n) равнялось O (g (n) + h (n)), а затем доказать это, используя первые утверждения.   -  person Paul Hankin    schedule 23.04.2018

Ответы (1)


arrow_upward
1
arrow_downward

Формально, используя определение Big-O-Notation, это можно было бы сделать так, как это сделал Ганс Хиттель здесь.

Доказательство:

введите здесь описание изображения

person Kristianmitk    schedule 22.04.2018