Komplexität von Algorithmus [gelöst]

[Francesco]

Guten Abend,

ich soll überprüfen ob folgende Behauptung stimmt:

$\frac{n^5}{17}\in\Omega(n^4)$

Die Definition von $f\in\Omega(g)$ lautet:

$f\in\Omega(g)\Leftrightarrow\exists~n_0\in\mathbb{N},~c\in\mathbb{R}^+:\forall~n\ge n_0: c\cdot g(n)\le f(n)$

Mein Lösungsansatz lautet:

$c\cdot n^4\le\frac{n^5}{17}\Leftrightarrow c\le\frac{n}{17}\Leftrightarrow c\cdot 17\le n$

Mit der Wahl von $c\ge1$ und $n_0=17$, ist diese Ungleichung erfüllt und die Behauptung bewiesen.

Ich stehe grade total auf dem Schlauch und weis nicht ob dies richtig ist. Kann mir da eventuell wer helfen?

Liebe Grüße

[Liz]

@Francesco Guten Morgen, ich bin mir nicht ganz sicher aber du hast

$\frac{n^5}{17}\in\Omega(n^4)$

Gesucht ist also $c\in\mathbb{R}^+, n_0\in\mathbb{N}$ so dass :

$\forall~n\ge n_0: \frac{n^5}{17}\ge c\cdot n^4$

$\Leftrightarrow \frac{n}{17}\ge c$

$\Leftrightarrow n\ge c \cdot 17$

@hustbaer stimmt

[hustbaer]

@Liz
Er muss nur zeigen dass für passend gewählte n0 und c die Ungleichung erfüllt ist.
Nicht dass sie für alle n0 und c erfüllt ist. Das wäre Quatsch, da man bei fast allen Funktionen mit c = 0 ein Problem bekommt.

@Francesco
Bin kein Mathematiker, aber ich denke das ist so korrekt.

[hustbaer]

@Liz
ps: Da steht auch $c\in\mathbb{R}^+$, also ist $c=0$ gar nicht erlaubt. Wäre auch Quatsch es zu erlauben

[Liz]

@hustbaer da hast du natürlich recht, in dem Fall wäre aber für $n = 0$ und $c = 0$ die Ungleichung sogar erfüllt. Hatte gestern verpeilt das es um $\Omega$ geht.

[Francesco]

Vielen Dank