Hallo,
ich bin erst 16 und bin wohl noch nicht so weit wie die meisten hier, aber ich hätte dennoch gerne eine Frage.
Ich verstehe zwar die O Notation (wie man es nimmt), aber ich habe gewisse Probleme beim Beweisen.
Als Beispiel:
Es wird gefragt ob
i) 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 mein Lehrer 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?
Danke sehr