0 Daumen
715 Aufrufe

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?

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

> 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.

Avatar von 105 k 🚀

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, n0, sodass für alle n ≥  n0 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, n0, sodass für alle n ≥  n0

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.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community