O-Kalkül zeigen, widerlegen.a) f(n) = 2n und g(n) = n, so ist f ∈ O(g). b) f(n) = n^3 und g(n) =n^2, so ist f ∈ O(g)

Question

Hier ist meine Aufgabe , hoffentlich könnt ihr mir helfen um sie zu verstehen;

Definition:

Durch das O-Kalkül wird die Menge von Funktionen beschrieben welche höchstens
so schnell wachsen wie eine gegebene Vergleichsfunktion. Die Menge der
von (groß) O beschriebenen Funktionen wird definiert durch:

      O(g) := {ƒ | ∃c∃n₀ : 0≤ |ƒ(n)| ≤ c* |g(n)| ∀n > n₀ }

 

Dabei gilt:

 

    g(n) = g,  ℕ → ℝ := Vergleichsfunktion

    f(n) = ƒ , ℕ → ℝ := untersuchte Funktion

    c∈ ℝ_>0 := konstanter Faktor

    n₀ ∈ ℕ := Schranke

Zeige oder widerlege folgende Behauptungen. Es ist kein formeller Beweis
nötig.

 

a) Sei f(n) = 2n und g(n) = n, so ist f ∈ O(g).

b) Sei f(n) = n³ und g(n) =n ² , so ist f ∈ O(g)

 

Eigentlich es gibt noch c,d,e,...Aber zuerst will ich verstehen wie ich die a und b  lösen kann.

Und danach kann ich den Rest machen , glaube ich

Ich bitte euch ausführliche Lösung hier zu stellen.

 

 

Gruß Jensen.

 

 

Answer 1

a) Sei f(n) = 2n und g(n) = n, so ist f ∈ =O(g).

Es muss also gelten

|f(n)| ≤ c * |g(n)|
2n ≤ c * n
2 ≤ c

Das ist erfüllt. Damit stimmt die Aussage.

b) Sei f(n) = n^3 und g(n) =n^2 , so ist f ∈ O(g)

|f(n)| ≤ c * |g(n)|
n^3 ≤ c * n^2
n ≤ c

Das ist nicht erfüllt und damit die Aussage wiederlegt.

Comments

Hi Mathecoach,

Kannst du mir sagen , wie vergleichst z.B bei a)    2 ≤ c ?

Ich meine woher weist du , dass 2 kleiner als c ist ?

Gruß Jensen!

---

@Jensen: Du musst 2 ≤ c umgekehrt lesen.  Für jedes c ≥ 2 ist die Bedingung in der Definition von O(g) erfüllt. z.B. für c=2. Deshalb ist a ok.

bei b)  c ≥ n findest du kein c, für das diese Bedingung immer erfüllt sein wird, weil n beliebig wachsen kann. Deshalb Antwort bei b) : nein.