Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » O Notation beweisen - asymptotische Schranken

O Notation beweisen - asymptotische Schranken

Universität / Fachhochschule

Sonstiges

Tags: Asymptotische Schranken, Beweis, O-Notation, Sonstig

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
IamDS

IamDS aktiv_icon

20:11 Uhr, 17.03.2021

Antworten
Ich sitze schon seit längerem an diesen eigentlich Recht einfachen Beispiel bezüglich der O-und Θ-Notation.
Wir sollten mit der Definition:

O(g):=f∣∃c∈R+,∃no∈N,∀n>n0:f(n)≤cg(n).

Θ(g):=f∣∃c1,c2∈R+,∃no∈N,∀n>n0:c1g(n)≤f(n)≤c2g(n).

arbeiten und uns Beispiele für f und g überlegen, beispielsweise f=n und g=n2.

Es seien f,g:N→R+. Beweisen oder widerlegen Sie:
f∈O(g)⇔g∈O(f)
f∈Θ(g)⇔g∈Θ(g)

Vielleicht könnte mir jemand erklären wie man so etwas richtig beweist.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Hierzu passend bei OnlineMathe:
Online-Nachhilfe in Mathematik
Antwort
DrBoogie

DrBoogie aktiv_icon

20:26 Uhr, 17.03.2021

Antworten
f∈O(g)⇔g∈O(f)

Das ist falsch. Denn wenn f(n)=n und g(n)=n2, dann gilt f(n)≤g(n), also f∈O(g). Aber wenn g∈O(f) gelten würde, müsste g(n)=n2≤cf(n)=cn für alle n>n0 gelten. Daraus folgt c≥n für alle n>n0 und das kann nicht funktionieren für eine feste Zahl c. Also g∉O(f).


f∈Θ(g)⇔g∈Θ(f)

Das ist richtig. f∈Θ(g) => c1g(n)≤f(n)≤c2g(n) für n>n0 => 1c2f(n)≤g(n)≤1c1f(n) für n>n0 => g∈Θ(f).
Andere Richtung genauso.
Frage beantwortet
IamDS

IamDS aktiv_icon

20:45 Uhr, 17.03.2021

Antworten
Vielen Dank! Ich hatte schon sowas ähnliches angenommen aber ich tue mir leider etwas schwer das Ganze mathematisch korrekt auszudrücken. Das hilft mir bei den anderen Aufgaben sehr weiter.