Beweisen von Ungleichungen mit O-Notation

Question

Frage:

Meine Aufgabe besteht darin Ungleichungen mit O-Notation zu beweisen.Als Hinweis ist gegeben:

Zu einem korrekten Beweis für O(f(n)) <= O(g(n)) gehört die
Angabe einer Konstante c > 0 und eines N (Element der natürlichen Zahlen), sodass für alle n >=N gilt: f(n) <= c · g(n).

Als Bsp einer der Aufgaben:

O(log(n)) <= O(n^(1/2))

--> laut Internetrecherche mit Induktion mögl. oder mit Abschätzungen

Problem ist, dass ich nicht so ganz verstehe wie die Reihenfolge des Beweis sein sollte und wie man c und N wählt.

Kann mir Jemand auf die Sprünge helfen?

Answer 1

Schau dir die Graphen der beiden Funktionen an.

Comments

Hab ich gemacht, aber was soll das mir bei diesen beiden Funktionen groß bringen? Weil n^(1/2) ist immer überhalb von log(n).

Was soll man dann für N und c wählen? Oder ist das dann egal, weil dann die Ungleichung immer gilt?

---

Weil n^1/2 ist immer überhalb von log(n).

\(N = 0, c = 1\).

Oder ist das dann egal, weil dann die Ungleichung immer gilt?

Mathematisch betrachtet ist es egal.

Praktisch gesehen musst du natürlich noch beweisen, dass tatsächlich

        \(\log n \leq c\cdot n^{\frac{1}{2}} \quad \forall n>N\)

ist. Und da könnte es sinnvoll sein, ein größeres \(N\) zu wählen oder ein anderes \(c\).

---

Kannst anhand von dieser Aufgabe: O(2^n) <= O(n!) mir zeigen wie der Beweis aussehen würde? Weil irgendwie verstehe ich nicht, wie c und N wählen soll, also ich verstehe nicht auf was man da ahten soll.

---

anhand von dieser Aufgabe: O(2ⁿ) <= O(n!)

\(N = 4, c=1\)

wie c und N wählen soll, also ich verstehe nicht auf was man da ahten soll.

Darauf dass der Graph von \(n!\) für \(n>N\) über dem von \(2^n\) verläuft.

Falls das nicht hinhaut, dann nimmt man ein größeres \(c\). GeoGebra hat dazu Schieberegler.

---

Okay so ist das also gemeint. Und den Beweis mit Induktion zu machen sollte dann passen, oder?

---

Ja, sollte passen.

---

Okay super, Danke für deine Mühe :)