Mostre que $ o (\ text {max} \ {f (n), g (n) \})= o (f (n) + g (n)) $

Question

Mostrar que $ o (\ text {max} \ {f (n), g (n) \})= O (f (n) + g (n))$

Posso manter a mesma constante $ c $ em cada um dos casos?

Considere dois casos: $$ 1) F (n)> g (n); o (\ text {max} \ {f (n), g (n) \}) ⇒ O (F (n)) \ Rightarrow D (n) ≤C⋅F (n); c> 0 $$ $$ 2) f (n) ≤g (n); o (\ text {max} \ {f (n), g (n) \}) ⇒o (g (n)) \ Rightarrow e (n) ≤C⋅g (n); c> 0 $$ Combinando os 2 casos rendimentos: $$ D (n) + E (N) ≤C⋅F (n) + C⋅g (n) $$ $$ D (n) + E (n) ≤C⋅ (F (n) + g (n)) $$ Que é a definição de $ o (f (n) + g (n)) $

Answer 1

Eu acho que a prova é boa, exceto pelo fato de que você usou o mesmo castador em dois eqns diferentes.Mesmo se você usar (e você deve usar, porque a constante escolhida é arbitrária) duas contas diferentes dizem C1 e C2, a solução irá implicar a mesma.