0 Daumen
940 Aufrufe

ich komme leider bei dieser Aufgabe nicht weiter. Könnte jemand mir helfen oder zumindest einen Ansatz zeigen?


Aufgabe:

Beweisen Sie formal, dass fu¨f : NR>0,n(n+9)2 die Eigenschaft fO(n2) gilt. \text{Beweisen Sie formal, dass für } f : \mathbb{N} \rightarrow \mathbb{R} ^{\gt 0}, n \rightarrow (n + 9)^{2} \text{ die Eigenschaft } f\in Ο (n^{2}) \text{ gilt.}

Avatar von
Beweisen Sie formal  \text{Beweisen Sie formal } \dots

Ist das das Gegenteil von "Beweisen sie mittels eines Hand-waving-Argumentes"? :-)

1 Antwort

0 Daumen

Für n18n \geq 18 gilt n218nn^2 \geq 18n und n281n^2 \geq 81.

Für n18n \geq 18 ist also

        (n+9)2=n2+18n+81n2+n2+n2=3n2(n+9)^2 = n^2 + 18n+81\leq n^2 + n^2 + n^2 = 3n^2.

Avatar von 107 k 🚀

Danke dir auf jeden Fall erstmal für die schnelle Antwort. Wie würde man diesen Ansatz noch als mathematisch korrekten Beweis verfassen? Haben Beweise erst vor kurzem gemacht, deswegen bin ich da noch ein bisschen Ahnunglos :D

Das ist ein mathematisch korrekter Beweis.

Was du noch machen könntest ist, darzulegen, warum die Ungleichungen n218nn^2 \geq 18n und n281n^2 \geq 81 gültig sind und wie die Ungleichung (n+9)23n2(n+9)^2 \leq 3n^2 zu der Definition on O(n2)O(n^2) passt, was also in

        fO(g)    NN,c>0nN : f(n)cg(n)f\in O(g) \iff \exists N\in\mathbb{N}, c>0 \forall n\geq N: \left|f(n)\right|\leq c\cdot \left|g(n)\right|

das NN und das cc ist.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
1 Antwort
1 Antwort
Gefragt 28 Nov 2021 von mathe_dummy
1 Antwort
Gefragt 7 Mai 2021 von Gast
1 Antwort