Landau Symbole und Definitionen

Question

Beweisen Sie, dass 100√n = O(n). Ich würde sagen es ist falsch nur wie beweise ich so etwas korrekt. Brauche ich hier die Definition von groß O?

Answer 1

> Ich würde sagen es ist falsch

Nein, es ist richtig.

> wie beweise ich so etwas korrekt

Indem du die Definition benutzt.

> Brauche ich hier die Definition von groß O?

Ja.

Comments

Ok, ich hab die Definition vor mir werde daraus aber einfach nicht schlau und weiß auch nicht wie ich es auf die Aufgabe anwenden könnte.

Es existieren Konstanten c > n, n_0, sodass für alle n ≥  n₀ gilt 0 ≤ f(n) ≤ c g(n)

Das bedeutet f(n) wird von g(n) dominiert. Die Konstanten darf ich wegfallen lassen das bedeutet √n = O(n) aber wie schreib ich sowas auf?

---

> Es existieren Konstanten c > n, n₀, sodass für alle n ≥  n₀

Wenn für alle n ≥ n0 etwas gelten soll, und c > n sein soll, dann kann c nicht konstant sein.

Bitte verwende die genaue Definition.

---

Sry verschrieben n sollte eine 0 sein, also 

Es existieren Konstanten c > 0, n0, sodass für alle n ≥  n0 gilt 0 ≤ f(n) ≤ c g(n)

---

> ... 0 ≤ f(n) ≤ c g(n)

Dabei ist

(1)        f(n) = 100√n,

(2)        g(n) = n.

Du musst zeigen, dass es ein c gibt, so dass

(3)        0 ≤ f(n) ≤ c g(n)

gilt. Dazu schauen wir uns erst ein mal an, was dieses c denn leisten muss. Einsetzen von (1) und (2) in (3) liefert

(4)        0 ≤ 100√n ≤ c n.

Der Teil 0 ≤ ... ist immer erfüllt. Konzentrieren wir uns auf 

(5)        100√n ≤ c n.

Löse diese Ungleichung nach c auf.

---

schaut dann so aus (100√n)/n ≤ c

---

Ist es dann richtig für n beliebig und für c = 100 einzusetzen?

Also (100√n)/n ≤ 100 

Dann wäre 100√n = O(n) richtig.

---

> schaut dann so aus (100√n)/n ≤ c

Sieht gut aus.

> Ist es dann richtig für n beliebig und für c = 100 einzusetzen?
> Also (100√n)/n ≤ 100 

Das passt nicht. Zum Beispiel hast du für n=0,64

        (100√n)/n

        = (100√0,64)/0,64

        = (100·0,8)/0,64

        = 125 > 100.

Trotzdem ist c=100 eine gute Wahl, weil du nämlich noch ein Ass im Ärmel hast.

Ok, vielleicht nicht im Ärmel, aber in dem Satz "Es existieren Konstanten c > 0, n0 ...".

---

Ja stimmt hätte mich besser Ausdrücken müssen, da es einen Fall gibt bei dem (100√n)/n ≤ c stimmt. Stimmt es auch ? Die 100 habe ich gewählt weil es vor der Wurzel vorkommt.

---

Der Satz "Es existieren Konstanten c > 0, n0 ..." verlangt nicht nur, dass du einen Wert für c bestimmst, sondern auch, das du einen Wert für n0 bestimmst.

Das hast du noch nicht gemacht. Ich habe deshalb gemeinerweise angenommen, dass

        n0=0

ist. Deshalb durfte ich

        n = 0,64

wählen. Und dann gilt eben nicht (100√n)/n ≤ 100. Finde heraus, für welche Werte von n die Ungleichung

        (100√n)/n ≤ 100

gilt. Der kleinste dieser Werte ist dann dein n0.

---

naja das wäre dann wohl 1 .) 

---

Das sehe ich auch so.