Informatiker Board | Druckvorschau: gross O notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- gross O notation (http://www.informatikerboard.de/board/thread.php?threadid=1781)

Geschrieben von Dobby1 am 14.01.2014 um 14:43:

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?

Geschrieben von spazzpp2 am 11.04.2014 um 00:13:

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]$