O-Notation Rechenregel Beweis

Question

ich habe etwas Probleme mit der Formulierung des Beweises dieser Aufgabe. Ich denke, dass es ein Widerspruch sein wird durch den Regel der Transitivität, bin ich aber nicht sicher. Wenn jemand helfen würde, wäre ich super denkbar <3

Aufgabe:

Gegeben seien die Funktionen f(n) und g(n). Beweisen oder widerlegen Sie:

Problem/Ansatz:

Falls g = O(f) und h = O(f), dann gilt auch g = O(h)

Answer 1

Überlege dir mal folgendes. Du hast zwei Funktionen g und h, die bis auf bestimmte Konstanten nur höchstens so schnell wachsen wie f. Muss, dann auch immer gelten, dass g bis auf eine bestimmte Konstante nur höchstens so schnell wie h wächst?

Answer 2

Im Falle

(I) g,h € O(f)

gilt

h(n) < c * f(n) für n → unendlich
g(n) < c * f(n) für n → unendlich

Aus diesen beiden Bedingungen folgt nicht zwingend

g(n) < c * h(n) für n → unendlich

was g € O(h) entsprechen würde. Damit ist die Behauptung widerlegt.