Zeige, das Funktion f(n) Element von O(g(x))

Question

gegeben sind in der Aufgabe zwei Funktionen, bei denen ich bestimmen soll, ob g(n) Element von O(f(n)) ist.

g(n) = 4815*n²
f(n) = 1/162342*n³

Meine Ideen:
Wenn ich es richtig verstanden habe, sind Summanden und konstante Faktoren bei der Bestimmung der O-Notation uninteressant.

Daher müsste doch f(n) = O(n³) sein, korrekt?

Nun verstehe ich aber nicht, wie ich nun nachweisen kann, ob g(n) Element von O(n³) ist.

Answer 1

Du kannst über den Grenzwert von g(n) / f(n) gehen.

Wenn es einen Grenzwert gibt muss die Funktion f demnach obere Schranke von g(n) sein. Gibt es keinen Grenzwert so ist f keine obere Schranke da sie von der Funktion g(n) ab einem gewissen x eingeholt wird.

Veranschaulichen kannst du das in einem Graphen wo du beide Funktionen eingibst. Sollte es einen Grenzwert geben sieht man dass der eine Funktionsgraph den anderen niemals einholen wird.