0 Daumen
940 Aufrufe

Moin,

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.

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.
von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...