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))