Zeige, dass (log n)^log n in o(2^(n/2)) liegt.

Question

Hallo:)

Wie schon im Titel beschrieben, soll ich das zeigen.

Ich weiß, dass ich es über den Grenzwert zeigen könnte, wenn er 0 wäre. Ich finde dies aber meiner Meinung nach zu kompliziert, da der logn ^(log n) Teil leicht falsch abgeleitet werden kann.

Ich hab deshalb versucht das ganze über Induktion zu zeigen, scheitere da aber leider auch...

Induktionsanfang: n=2 ( da sonst 0^0)

1^1 < 2^1 =2

Induktionsschritt:n-> n+1

2^((n+1)/2 = 2^(n/2) * 2^(1/2) >=(IV) (log n)^(log n) * 2^(n/2)

Und da weiß ich nicht mehr weiter...

Würde mich über Ansätze freuen:)

Answer 1

Also wenn du die ,,Klein O Notation'' verwendest, musst, du das für beliebige Konstanten \( \alpha >0 \) zeigen. Es gilt mit \(f: \ \mathbb{N} \rightarrow \mathbb{R} \)

\(o(g):=\{f: \ \mathbb{N} \rightarrow \mathbb{R}: \forall \alpha >0 \ \ \exists n_0\in \mathbb{N} \ \ \forall n\geq n_0: 0\leq f(n) \leq \alpha\cdot g(n)\} \).

Und um dies für alle \(  n\geq n_0 \) zu zeigen, ist Induktion eine gute Wahl.