Mastertheorem, Rekursionsgleichung

Question

Aufgabe:

Benutzen Sie das Master-Theorem, um die Laufzeitklasse folgender rekursiver Funktionen T(n) zu
berechnen. Es kann angenommen werden, dass T(1) konstant und n eine Potenz von b ist.

T(n) = 16T( \( \frac{n}{4} \) ) + \( \sqrt{7n} \) ( \( \frac{n}{9} \) + n \( \sqrt{n} \) ) + 2⁹³

Problem/Ansatz:

Bei dieser Aufgabe sind wurzeln drinne und ist eine lange formel, wobei ich leider nicht weiß wie ich es anwenden soll, bzw. berechnen soll.. Könnt ihr mir dabei helfen bitte ? :(

Rejes

Comments

https://www.mathelounge.de/250381/master-theorem-rekursionsgleichung ist hier vielleicht die einzige Frage zu diesem Theorem, die bisher eine Antwort erhalten hat. Schau dir mal die Frage und die zugehörige Antwort an.

Vielleicht auch https://www.mathelounge.de/312848/losen-einer-rekursionsgleichung

Answer 1

Mastertheorem anwenden. Betrachte f(n), ob es asymptotisch schneller, langsamer oder gleich f(n) wächst.

a = 16, b = 4, f(n) = \( \sqrt{7n} \) (\( \frac{n}{9} \) + n\( \sqrt{n} \) ) + 2⁹³

Die Wurzeln in f (n) zu \( n^{\frac{1}{2}} \) umschreiben

\( 7^{\frac{1}{2}} \)  * \( n^{\frac{1}{2}} \) (\( \frac{n}{9} \) + n * \( n^{\frac{1}{2}} \) ) + 2⁹³

n und \( n^{\frac{1}{2}} \) in der Klammer zusammenfassen, ergibt:

\( 7^{\frac{1}{2}} \)  * \( n^{\frac{1}{2}} \) (\( \frac{n}{9} \) + \( n^{\frac{3}{2}} \) ) + 2⁹³

\( n^{\frac{1}{2}} \) jetzt in die Klammer reinmultiplizieren:

\( 7^{\frac{1}{2}} \) * ( \( n^{\frac{1}{2}} \) * (\( \frac{n}{9} \) + \( n^{\frac{3}{2}} \) ) + 2⁹³

Terme in der Klammer zusammenfassen

\( 7^{\frac{1}{2}} \) * ( \( \frac{n^{\frac{3}{2}}}{9} \) + n² ) + 2⁹³

Was wächst von allen Termen hier am schnellsten? Das n². Der Rest kann asymptotisch vernachlässigt werden. Also ist die Laufzeit von f (n) schon mal Θ (n²).

Jetzt gucken wir uns nur noch kurz an ob \( n^{logb(a)} \) schneller, langsamer oder gleich wächst.

\( n^{logb(a)} \) = \( n^{log4(16)} \) = n².

Wächst also asymptotisch gleich schnell => Master-Theorem 2. Fall anwenden

Θ (\( n^{logb(a)} \) * log (n))

= Θ (n² * log (n))