Доказательство правила большой суммы?

Question

Я не уверен, как формально доказать Правило Big O из сумм, то есть:

f1(n) + f2(n) is O(max(g1(n)),g2(n)) 

До сих пор я предполагал, следующее в моих усилий:

Пусть две константы c1 и c2 такие это c2 > c1. По определению Big O:

f1(n) <= c1g1(n) and f2(n) <= c2g2(n) 

Как продолжить? Разумно ли вводить числовые замены для переменных на этом шаге, чтобы доказать связь? Не зная g или f, это единственный способ, с которым я могу приблизиться.

Answer 1

Пусть

gmax = max(g1, g2), and gmin = min(g1, g2). 

Gmin является O (Gmax). Теперь, используя определение:

gmin(n) <= c*gmax(n) for n > some k 

Добавление Gmax (п) к каждой стороне дает:

gmin(n) + gmax(n) <= c*gmax(n) + gmax(n) for n > some k 
gmin(n) + gmax(n) <= (c+1)*gmax(n)  for n > some k 
g1(n) + g2(n) <= c'*gmax(n)    for n > some k 

Таким образом, мы имеем g1 + g2 является O (макс (g1, g2)).

Поскольку f1 + f2 равно O (g1 + g2), транзитивное свойство big-O дает нам f1 + f2 равно O (max (g1, g2)). QED.

Answer 2

Вам даже не нужно определение - просто разделите обе стороны на более быстро растущую функцию, возьмите предел в бесконечности, и более медленная функция будет приближаться к нулю (то есть она незначительна).

Answer 3

Я полагаю, я мог бы быть больше конструктивизма, я бы атаковать эту проблему так:

По определению Big-O, существуют положительные с , с , N , и N 2 таким образом, что

е (п) = с < г (п) для всех п> N

и

е (п) < = с г (п) для всех п> N

Пусть:

N '= макс (N , N)
с' = с + с
г '(п) = тах (г (п), г (п))

Тогда для всех п> N»мы имеем:

е (п) < = с г (п) < = с г '(п)
е (п) < = с г (п) = с < г '(п)
е (п) + F 2 (п) = с < _{1 4444093 +55713794460255508888 г '(п) + с г' (п) = c'g '(п)}

Следовательно, F (п) + F 2 (п) = О (г '(п)) = O (макс (г (п), г (п)))