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} \) ) + 293
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}} \) ) + 293
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}} \) ) + 293
\( n^{\frac{1}{2}} \) jetzt in die Klammer reinmultiplizieren:
\( 7^{\frac{1}{2}} \) * ( \( n^{\frac{1}{2}} \) * (\( \frac{n}{9} \) + \( n^{\frac{3}{2}} \) ) + 293
Terme in der Klammer zusammenfassen
\( 7^{\frac{1}{2}} \) * ( \( \frac{n^{\frac{3}{2}}}{9} \) + n² ) + 293
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))
