Gegeben sei die rekursive Laufzeitgleichung T(n) . Zeigen Sie mittels Induktion dass T(n) = ... gilt

Question

Aufgabe:

Gegeben sei die rekursive Laufzeitgleichung $T(n)$ mit:

$T(n)=\left\{\begin{array}{ll}1 & \text { für } n=1 \\8 \cdot T\left(\frac{n}{2}\right)+n^{2} \sqrt{n} & \text {für } n>1\end{array} .\right.$

Zeigen Sie mittels Induktion dass

$T(n)=(2+\sqrt{2}) \cdot n^{3}-(1+\sqrt{2}) \cdot n^{2} \sqrt{n}$

gilt.

Gehen Sie dafür davon aus, dass $n$ eine eine Zweierpotenz ist ( $n=2^{k}$ mit $k \in \mathbb{N}$ ).

Problem/Ansatz:

Das für n= 1 T(n) = 1 ist kann ich leicht beweisen durch einsetzten aber wenn ich n = n+1 einsetze komme ich nicht weiter ich habe auch schon versucht die Wurzeln als Exponenten zu schreiben. Ich komme mit meinem "Kochrezept"-Ansatz es einfach nach dem bisherigen Schema zu machen einfach nicht weiter.

Ich hab sogar schon das Muster-Theorem drauf angewendet aber das ist ja nicht die Lösung oder?

a = 8; b = 2; f(n) = $n^2\sqrt{x}$

γ = $\frac{af( \frac{n}{b})}{f(n)}$ = $\frac{8f( \frac{n}{2})}{f(n)}$ = $\frac{8 \frac{n^2}{4} \sqrt{\frac{n}{2}}}{n^2 \sqrt{n} }$ = $\frac{\sqrt{2}n^2 \sqrt{n}}{n^2 \sqrt{n} }$ = $\sqrt{2}$  > 1

Comments

Vom Duplikat:

Titel: rekursive Laufzeitgleichung gegeben

Stichworte: rekursiv,induktion,beweise,funktion,folge

Aufgabe:

Gegeben sei die rekursive Laufzeitgleichung

$T(n)$ mit:$T(n)=\left\{\begin{array}{ll}1 & \text { für } n=1 \\8 \cdot T\left(\frac{n}{2}\right)+n^{2} \sqrt{n} & \text {für } n>1\end{array} .\right.$

Zeigen Sie mittels Induktion dass

$T(n)=(2+\sqrt{2}) \cdot n^{3}-(1+\sqrt{2}) \cdot n^{2} \sqrt{n}$

gilt.

Gehen Sie dafür davon aus, dass $n$ eine eine Zweierpotenz ist ( $n=2^{k}$ mit $k \in \mathbb{N}$ ).

Problem/Ansatz:

ich weiß nicht wirklich wie man hier vorgehen könnte und würde mich über jede Hilfestellung freuen.

---

Vom Duplikat:

Titel: rekursive Laufzeitgleichung gegeben

Stichworte: rekursiv,funktion,injektiv,reihenfolge

Aufgabe:

Gegeben sei die rekursive Laufzeitgleichung

$T(n)$ mit:$T(n)=\left\{\begin{array}{ll}1 & \text { für } n=1 \\8 \cdot T\left(\frac{n}{2}\right)+n^{2} \sqrt{n} & \text {für } n>1\end{array} .\right.$

Zeigen Sie mittels Induktion dass

$T(n)=(2+\sqrt{2}) \cdot n^{3}-(1+\sqrt{2}) \cdot n^{2} \sqrt{n}$

gilt.Gehen Sie dafür davon aus, dass $n$ eine eine Zweierpotenz ist

( $n=2^{k}$ mit $k \in \mathbb{N}$ ).

Problem/Ansatz:

ich weiß nicht wirklich wie man hier vorgehen könnte und würde mich über jede Hilfestellung freuen.