O-Notation| Zeige oder widerlege

Question

ich bin gerade in der Klausurvorbereitung und habe eine Frage zur O-Notation. Wir haben ein paar Beispiele bekommen die wir lösen können. Allerdings weiß ich nicht wie man sowas macht da wir das nie in den Vorlesungen hatten. Kann mir jemand ganz kurz erklären wie sowas funktioniert?

a) 42n = Ο(n^2)
b) n^2 + 100n + 4 = Ο(n^3)

Wir haben natürlich noch mehr Aufgaben aber die möchte ich dann selber lösen...

Vielen Dank schonmal!

Comments

da wir das nie in den Vorlesungen hatten

Was Du nicht sagst. Keine Definition der O-Notation angegeben? Das ist dumm. Denn genau die (und sonst nichts) braucht man für die Aufgabe.

Answer 1

Die Aussage f = O(g) meint, dass die Funktion f nicht wesentlich schneller wächst als die Funktion g. Es handelt sich also nicht um eine Gleichung im üblichen Sinn. Als besser betrachte ich daher die Schreibweise f € O(g).

Die Aussage f € O(x^2) z.B. meint, dass die Funktion f "ungefähr" quadratisch wächst. Insofern sind die Aussagen a) und b) falsch.

Die O-Notation ist hier beschrieben https://de.wikipedia.org/wiki/Landau-Symbole.