0 Daumen
2,3k Aufrufe

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)

Avatar von

2 Antworten

0 Daumen

Ü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?

Avatar von 14 k
0 Daumen

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.

Avatar von 3,4 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
1 Antwort
Gefragt 7 Mai 2021 von Gast
1 Antwort
Gefragt 28 Nov 2021 von mathe_dummy

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community