Groß O Notation: Beweisen oder Widerlegen

Question

es gibt schon ein paar Themen zu diesem Gebiet, nur irgendwie leuchtet mir das Ende noch nicht ein.

Wenn ich jetzt als Beispiel habe:

f=5n³ + 5 -1

Zeigen sie das f∈O(n³) ist

Die Definition sagt f(n) < c * g(n) also ist

5n³ + 5 -1< c * n³  = 5 + 5/n³ - 1/n³    <  c

Von hier weg komme ich nicht mehr weiter. Wie interpretiere ich das jetzt richtig?

Comments

Wieso soll cn³= 5+5/n³-1/n³ gelten?Und wieso schreibt du die ganze Zeit 5-1 statt schlicht 4?Und du vergisst bei der Defintion die essentiellen Quantoren.

---

Mit dem = wollte ich nur die Umwandlung darstellen. Wenn ich n³ auf die linke Seite hole wird daraus 5 + 4/n³ <  c

Auf das mit der 4 habe ich noch gar nicht geachtet, aber hab es ausgebessert. ;)

Was fehlt denn noch?  ∃c > 0 sein was offensichtlich zutrifft. Reicht das etwa schon?

---

Die "Umwandlung"- in Fachsprache: Termumformung - stellt mit mit einem Äquivalenzpfeil dar. = steht hier für eine durchgehene /Un-)gleichungskette, zwei komplett verschiedene Sachen.Mit dem 4 ging ich eigentlich eher davon aus dass die Aufgabenstellung falsch abgeschrieben wurde und es eher f(n)=5n³+5n-1 o.ä. sein soll. Und wenn die Existenz von c>0 ja offensichtlich zutrifft wieso sie nicht einfach zeigen, oder ist sie doch nicht offensichtlich?Und nein selbst dann reicht das nicht, da fehlt noch ein Quantor. Es ist unerlässlich Defintionen genau zu lesen.

Answer 1

Die Definition sagt f(n) < c * g(n)

wohl eher: Es gibt ein c >0 mit f(n) < c * g(n) für alle

hinreichend großen n aus IN.

also erst recht wenn es gint ein k mit  lim f(n) / g(n) = k

In deinem Fall ist lim (5n³ + 5 -1 ) / n^3   = 5 also alles paletti.