Zeigen Sie dieses $ o (\ text {max} \ {f (n), g (n) \})= o (f (n) + g (n)) $

Question

zeigen, dass $ O (\ Text {max} \ {f (n), g (n) \})= o (f (n) + g (n))$

Kann ich den gleichen konstanten $ c $ in jedem der Fälle halten?

Betrachten Sie zwei Fälle: $$ 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 $$ Kombination der 2 Fälle Erträge: $$ D (N) + E (n) ≤ c⋅f (n) + c⋅g (n) $$ $$ D (N) + E (N) ≤ c⋅ (f (n) + g (n)) $$ Welches ist die Definition von $ o (f (n) + g (n)) $

Answer 1

Ich denke, der Beweis ist in Ordnung, außer der Tatsache, dass Sie in zwei verschiedenen EQNs gleiche Kostant verwendet haben.Auch wenn Sie verwenden (und Sie müssen verwendet werden, da die Konstante, weil Sie möchten, willkürlich) zwei verschiedene Konsenten sagen, dass C1 und C2 die gleiche impliziert.