O-Notation Zeigen Sie

Question

Aufgabe:

\( \frac{4 n^{2}-3 n+2}{7 n+3} \) ist \( O(n) \)

Hallo.

Wie zeige ich, ob diese Behauptung stimmt?

Ich muss doch beweisen, dass es ein C>0 gibt, welches \( \frac{4n²-3n+2}{7n+3} \) <= C(n) erfüllt. Wie mache ich das?

Answer 1

Aloha :)$$f(n):=\frac{4n^2-3n+2}{7n+3}=\frac{4n^2\,\overbrace{+\frac{12}{7}n-\frac{12}{7}n}^{=0}-3n+2}{7n+3}$$$$\phantom{f(n)}=\frac{4n^2+\frac{12}{7}n-\frac{12}{7}n-\frac{21}{7}n+2}{7n+3}=\frac{4n^2+\frac{12}{7}n-\frac{33}{7}n+2}{7n+3}$$$$\phantom{f(n)}=\frac{4n^2+\frac{12}{7}n}{7n+3}-\underbrace{\frac{\frac{33}{7}n-2}{7n+3}}_{>0\;\text{für }n\ge1}<\frac{4n^2+\frac{12}{7}n}{7n+3}=\frac{4n\left(n+\frac{3}{7}\right)}{7\left(n+\frac{3}{7}\right)}=\frac{4}{7}n$$Damit haben wir gezeigt:$$\frac{4n^2-3n+2}{7n+3}<\frac{4}{7}n\quad\text{für alle}\quad n\ge1\quad\checkmark$$Das heißt \(f(n)\in O(n)\).

Comments

Danke für die Antwort, wie kommst du auf die \( \frac{12}{7} \) n ?

---

Nun kann ich nicht für Tschakabumba sprechen, doch meine Vermutung ist, dass die Idee es auseinander zu pflücken und vorne  mit (n +\( \frac{3}{7} \) ) zu kürzen, der Auslöser für \( \frac{12}{7} \)n war.

Warum aber aus der 3 im Nenner unten dann plötzlich eine 2 wurde, das versteht wohl nicht einmal Tschakabumba.

---

Er hat also praktisch von hinten nach vorne gerechnet?

---

Ja, so vermute ich es, wobei ich keine Ahnung habe, was O(n) bedeutet.

Ich verstehe alles, bis auf die 2 im Nenner und das O(n)

---

Ja, die \(\frac{12}{7}n\) sind von hinten nach vorne gerechnet. Ich wollte so ausklammern können, dass etwas wie \(\text{Faktor}\cdot n\) übrig bleibt. Das ist ja für den Nachweis der Mitgliedschaft in \(O(n)\) nötig.

Die 2 ist ein Tippfehler... 2 und 3 liegen so schrechlich nahe zusammen auf der Tastatur. Zur Minderung von Hogars Blutdruck, habe ich das bereits korrigiert ;)

---

Ich bin ganz ruhig geblieben, da ich ohne nachzurechnen,  davon ausgehe, dass auch diese Aussage richtig

Answer 2

Du musst beweisen, dass es ein C und ein N gibt, so dass

        \(\frac{4n²-3n+2}{7n+3} < C·n\)

für alle \(n > N\) ist.

Führe dazu die Polynomdivision durch. Wähle C so, dass es größer als die Steigung des linearen Teils ist.

Comments

Bedeutet O(n), dass es ein C gibt, dass

O(n)<C*n für alle n>N

Das erinnert mich an die Cauchyfolge, nur dass  diese Folge nicht gegen einen Grenzwert konvergiert , sondern in einem Sektor bleibt

Würde dies bedeuten, dass der Rang des Zählers nur um 1 größer sein darf als der des Nenners?

Es fühlt sich merkwürdig an, wenn man keine Ahnung hat und trotzdem mitreden will. Dann steht der Satz auf dem Bildschirm und man drückt nicht auf Senden.