Hallo,
hoffentlich ist das hier der richtige Ort für die Frage.
Also ich habe ein paar Fragen bzgl. des Wachstums von zwei Funktionen. Irgendwie habe ich es in der Übung und in der Vorlesung nicht richtig verstanden aber hoffentlich könnt ihr mir es verständlich erklären. Ich glaube dass es auch nicht so schwer ist.
In der Vorlesung hatten wir über Obere, Untere Schranken besprochen und über die genaue Laufzeit.
Obere Schranke: zb. f wächst höchstens so schnell wie g
es gilt zzg.: f(n) <=cg(n)
Untere Schranke: f wächst mind. so schnell wie g
es gilt zzg.: cg(n) <= f(n)
und f wächst wie g
cg(n) <=f(n)<=dg(n)
... für jeweils geeignete Konstanzen c,d,n0 >0
Ich habe jetzt eine Aufg. in der ich das Wachstum zweier Funktionen miteinander vergleichen soll. Ich soll entweder angeben ob f(n) = O(g(n) und/oder g(n) = O(f(n)) ist. Mit Begründung..
Ich habe mir folgendes gedacht:
a) f(n) = 100n + log n
g(n) = n + (log n)^2
für f(n) = O(g(n):
ist also zzg: dass folgendes gilt:
100n + logn <= c ( n+(log n)^2) für alle n>n0
Kann ich dann als Antwort schreiben, dass wenn c=100 und n=10 diese Ungleichung immer erfüllt sein muss? und wie sieht es bei g(n) = O(f(n)) aus?
Wäre echt super wenn mir jemand da ein bischen weiterhelfen könnte und einen Tipp geben kann wie man relativ schnell auf solche Lsg. kommen kann,
Gruß!