Startseite » Forum » O-Notation, Limes, Beweis

O-Notation, Limes, Beweis

Universität / Fachhochschule

15:30 Uhr, 04.04.2018

Hallo,

ich kann die Aufgabe nur widerlegen; nicht beweisen.

Stimmt meine Lösung:

T (n) = \frac{n \cdot (n + 1)}{2} = \frac{n^{2} + n}{2}

(das ist gegeben)

T (n) = O (n^{2})

lim_{n \to \infty} \frac{\frac{n^{2} + n}{2}}{n^{2}} = (\frac{n^{2} + n}{2}) \cdot \frac{1}{n^{2}} = \frac{n^{2} + n}{2 n^{2}} = \frac{n \cdot (n + 1)}{2} n^{2}

= \frac{n + 1}{2} n = 0

O (n^{2}) = T (n)

lim_{n \to \infty} \frac{n^{2}}{\frac{n^{2} + n}{2}} = (n^{2}) \cdot \frac{2}{n^{2} + n} = \frac{2 n^{2}}{n^{2} + n} = \frac{2 n^{2}}{n (n + 1)}

= 2 \frac{n}{n + 1} = \infty

15:44 Uhr, 04.04.2018

Hallo,

du sollst doch nicht

T (n) = O (n^{2})

zeigen, sondern

T (n) = Θ (n^{2})

.
Der Limes von

\frac{n^{2} + n}{2 n^{2}}

ist nicht

0

, sondern

\frac{1}{2}

.

Gruß ermanus

15:48 Uhr, 04.04.2018

Danke.

In meinen Skripten steht:

f = Θ (g),

falls

f = O (g)

und

g = O (f)

15:53 Uhr, 04.04.2018

Oh, das kann ich natürlich nicht wissen :(
Bin nun erst mal eine Weile offline ...

15:59 Uhr, 04.04.2018

Doch noch auf die Schnelle:
wenn du dann die Limites richtig (!)

;-)

berechnet hast, dürfte es
wohl klappen.
Von der Schreibweise her:

T (n) = O (n^{2})

, aber

n^{2} = O (T (n))

, so müsste es heißen.

16:11 Uhr, 04.04.2018

Danke,

mir ist auch gerade mein Fehler aufgefallen.

Der erste Grenzwert ist

\frac{1}{2};

der zweite 2.

Damit müsste es bewiesen sein.

1421018

1421009

	Status: nicht eingeloggt	Noch nicht registriert?