0 Daumen
582 Aufrufe

ich versuche eine Rekursionungleichung mal ohne das Mastertheorem durch wiederholtes einsetzen zu lösen:

Gegeben:

$$t(1)\quad =\quad 1\\ t(n)\quad =\quad 16t(\left\lceil \frac { n }{ 2 }  \right\rceil) +{ n }^{ 4 }$$

Mit dem Mastertheorem kommt ∈O(nlogn) raus.

Nun setze ich die Formel in sich ein:


$$\quad 16(16t(\left\lceil \frac { n }{ 4 }  \right\rceil )+{ \left( \frac { n }{ 2 }  \right)  }^{ 2 })+{ n }^{ 4 }\quad =\quad { 16 }^{ 2 }\cdot t(\frac { n }{ { 2 }^{ 2 } } )+16\cdot { \left( \frac { { n }^{ 4 } }{ { 2 }^{ 4 } }  \right)  }\quad +{ n }^{ 4 }\quad \\ ={ 16 }^{ 2 }\cdot t(\frac { n }{ { 2 }^{ 2 } } )+{ n }^{ 4 }+{ n }^{ 4 }$$

Bei wiederholtem einsetzen entsteht:

$$={ 16 }^{ k }\cdot t(\frac { n }{ { 2 }^{ k } } )+{ kn }^{ 4 }$$


Wie komme ich hier weiter?

Im Skript wird bei einer ähnlichen Aufgabe nun einfach behauptet "für n=2k gelte".

Das mache ich nun auch:

$$={ 16 }^{ k }\cdot 1+{ kn }^{ 4 }\\ ={ 16 }^{ k }+\quad { n }^{ 4 }\cdot logn\quad \quad \quad \quad |\quad da\quad n={ 2 }^{ k }\quad \Rightarrow logn\quad =k\\ ={ 16 }^{ logn }+{ n }^{ 4 }\cdot logn\quad$$

Das liegt aber nicht in der O Klasse die beim Mastertheorem rauskommt, was mache ich falsch?


Danke und Gruß,

DunKing

Avatar von

Wie kommst du auf

Rekursionungleichung

?

Bis jetzt ist nirgends ein Ungleichheitszeichen zu sehen.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
+1 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community