0 Daumen
2,3k Aufrufe

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

g(n) = 4815*n2
f(n) = 1/162342*n3

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(n3) sein, korrekt?

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

Avatar von

1 Antwort

0 Daumen
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.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community