Theta und Konsorten Beweis

Question

Seien \( f, g: \mathbb{N} \rightarrow \mathbb{R}_{>0} \). Dann folgt aus \( f(n)=O(g(n)) \), dass \( (f+g)(n)=\Theta(g(n)) \) ist.

Wie beweist man das?

Answer 1

Hallo,

Wenn \(f=0(g)\) ist, dann existiert also ein m, so dass für \(n \geq m\) gilt: \(f(n) \leq c g(n)\). Für diese n gilt auch:

$$g(n) \leq f(n)+g(n) \leq (c+1) g(n)$$

Fertig.

Gruß Mathhilf

Comments

Vielen lieben Dank