O Notationen beweisen oder widerlegen

Question

bin gerade dabei das hier zu beweisen bzw. zu widerlegen  f=Ω(g)∧g=Ω(h)⟹f=Ω(h), aber wie fängt man hier an? Muss ich auf die Definitionen achten? Ich weiß nicht was ich damit anfangen soll.

LG

Answer 1

Von er Defintion von Ω haben wir folgendes: $$\exists k>0 \ \exists n_0 \ \forall n>n_0 : f(n)\geq k\cdot g(n)$$ und $$\exists \lambda>0 \ \exists n_1 \ \forall n>n_1 : g(n)\geq \lambda\cdot h(n)$$ Wir bekommen also folgendes $$ f(n)\geq k\cdot g(n)\geq k\cdot \left(\lambda\cdot h(n)\right)=\left(k\cdot \lambda \right)\cdot h(n)$$ Es gibt also ein  $$k\cdot \lambda >0$$ und $$n_2:=\max \{n_0, n_1\}$$ sodass $$ f(n)\geq \left(k\cdot \lambda \right)\cdot h(n)$$ Davon folgt es dass f = Ω(h).