Forum / Wissenschaft und Technik / O Notation

Ich habe da ein Problem

Als Beispiel:

Es wird gefragt ob
a) Summe (2i+1) = O(n²) ist

Nach Umformen würde für mich folgendes herauskommen

2*( (n (n+1) ) / 2) + n = n² +2n <= c * n²
woraus folgt c>= 1 + (2/n) ----> c = 3

So weit so gut.

Bei
ii) (n+1)! = O(n!)
hätte ich es wie folgt gemacht

(n+1)! = n! (n+1) <= c * n!

(n+1) <= c

Bis hier hin. Mein Beweis wäre in der nächsten Zeile fertig gewesen. Nun sagt man mir aber, dass dies schon der Widerspruchsbeweis ist, nach dem Satz des Archimdeses (Also dieses, jede reelle Zahl wird von einer natürlichen übertroffen)

Ich komme jetzt allerdings nicht dahinter, warum ich dieses Argument bei
n+1 <= c anwenden kann und bei c>= 1 + (2/n) nicht?

[zustimmen]

Rifleman

- 40
Experte (offline)

Dabei seit 09.2003
1540 Beiträge

Geschrieben am: 29.12.2010 um 18:07 Uhr

Zitat von LatinBaby:

Ich komme jetzt allerdings nicht dahinter, warum ich dieses Argument bei
n+1 <= c anwenden kann und bei c>= 1 + (2/n) nicht?

c ist beliebig, aber fest, das heisst es muss ein c geben, für das die Ungleichung für alle n richtig ist.
Bei c >= 1 + (2/n) ist das möglich, da ein n existiert, für das dir rechte Seite maximal ist.
Bei n+1 <= c sieht man, dass für jedes beliebige c ein n gewählt werden kann, so dass die Ungleichung falsch ist. Also ist die Behauptung falsch.

[zustimmen]

Es sind die kleinen Dinge, die einen zum Wahnsinn treiben.

LatinBaby

- 36
Halbprofi (offline)

Dabei seit 06.2008
140 Beiträge

Geschrieben am: 29.12.2010 um 18:22 Uhr

Coole Sache..versteh ich sogar...

vielen dank. Du bist toll! ;)

[zustimmen]

[Antwort schreiben]

Forum / Wissenschaft und Technik