Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 1 von 1 Treffern
Autor Beitrag
Thema: O-Notation
AP0

Antworten: 1
Hits: 5.325
O-Notation 28.01.2019 20:33 Forum: Berechenbarkeits- und Komplexitätstheorie


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 smile
Zeige Beiträge 1 bis 1 von 1 Treffern