Groß-O-Notation: Zeigen oder widerlegen

Question

Hallo.

Ich habe eine Verständnisfrage zu einer Aufgabe.

Ich soll zeigen oder widerlegen, dass

34 + 23 + 17 = O(1)

Bei der nächsten Aufgabe

2n³ + 6n² + 5n + 47 = O(n³)

Grundsätzlich gilt doch, dass ich abschätzen kann, dass die größte Potenz die Wachstumsgeschwindigkeit angibt.

Bei der ersten Aufgabe ist es n⁰ = 1, bei der zweiten eben n³.

Aber wie beweise ich das jetzt mathematisch?

Answer 1

Zu 2. Zeige dass es ein C>0 gibt, so dass für hinreichend große n

|2n³ + 6n² + 5n + 47| ≤ C·|n³|

ist.

Tipp: Für n> 1 ist

• 6n² < 6n³
• 5n² < 5n³
• 47 < 47n³

Answer 2

Du musst dich an die Definition nhalten

vielleicht war die ja so:

Es gilt T(n) = O ( g(n) ) wenn es positive c und no gibt,

so dass gilt T(n) ≤ c*g(n) für alle n > no und n aus N.

Dann nimmst du für das 1. Beispiel

c=75 und no=1 denn dann gilt für

alle n aus N:   wenn n>no, dann 34 + 23 + 17  ≤ c * 1

Das hängt zwar nicht von n ab, ist aber sicherlich richtig.

Bei dem 2. Fall hast du schon richtig n³ angegeben,

Und musst nun wieder zeigen ( ganz großzügig

etwa mit c=13 und no =  5 )

Für n≥50 gilt  2n³ + 6n² + 5n + 47 ≤  14n³  

zeigst du so:  Für alle n gilt

2n³ + 6n² + 5n + 47  ≤     2n³ + 6n³ + 5n³  + 47

=  13n³ + 47   und für n>4 ist n³ > 47 also

≥ 13n³ + n³ = 14n³  .    q.e.d.

Comments

Hier noch einmal ein Gedankenschritt.

---

Du kannst es ja andersherum hinschreiben.

Dann passt es doch.