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.