Geschrieben von AP0 am 28.01.2019 um 20:33:
O-Notation
Hallo zusammen,
ich habe eine Frage zur O-Notation bzw. eine Aufgabe, bei der ich nicht so recht weiter weiß:
Beweisen Sie die folgende Ungleichung. Zu einem korrekten Beweis gehört die Angabe einer Konstante c und eines N, sodass für alle
n >= N gilt: f(n) < c*g(n).
Hinweis: Benutzen Sie die die Definition der O-Notation und vollständige Induktion.
a) O(2^n) < O(n!).
Was mir hier noch nicht völlig klar ist, sind die Konstanten N und c. Wie in der Aufgabe steht, soll ja für alle n >= N gelten: f(n) < c*g(n).
Aber bedeutet das nicht, dass N davon abhängt, wie c gewählt ist? Bzw. wie würde ich hier mit der Induktion starten?
Ich hoffe, dass ihr mir helfen könnt
