gross O notation

14.01.2014, 14:43

Dobby1

gross O notation

Meine Frage:
Hallo,

ich habe eine aufgabe :
ich muss zwei monoton wachsende funktionen finden die von N0 nach N0 gehen für die muss gelten:
beide müssen monoton wachsend sein
f(n) ist nicht element O(g(n))
und g(n) ist nicht element O(g(n).

Meine Ideen:
so ich habe mir überlegt dass ich vielleicht eine beschränkte funktion nehmen könnte und eine nicht beschränkte, da es ja nur monoton wachsend und nicht streng monoton wachsend sein muss

aber wenn f(n) beschränkt ist, dass ist es ja element vonO(g(n)) und des darfs ja nichtz sein.

ist mein ansatz komplett falsch?

11.04.2014, 00:13

Auf diesen Beitrag antworten »

spazzpp2

Zitat:

f(n) ist nicht element O(g(n))
und g(n) ist nicht element O(g(n).

Wie kann denn $[latex]g(n) \notin \mathcal{O}(g(n))[/latex]$ gelten?

Lt. Wikipedia gilt:
$[latex]f \in \mathcal{O}(g) \iff \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty[/latex]$

Wenn
[latex]f = g[/latex]

,
dann gilt
$[latex]\limsup_{x \to a} \left|\frac{g(x)}{g(x)}\right| = \limsup_{x \to a} \left|1\right| < \infty[/latex]$
für alle $[latex]x \mid g(x) \neq 0[/latex]$ .

Es gilt also immer
$[latex]g \in \mathcal{O}(g(n))[/latex]$

Neue Frage »

Antworten »

gross O notation

Verwandte Themen