Aufgabe:
Benutze das Master-Theorem, um die Laufzeitklasse folgende rekursiver Funktion T(n) zu berechnen. Es kann angenommen werden, dassT(1) konstant und n eine Potenz von b ist.
16 T (\( \frac{n}{4} \)) + \( \sqrt{7n} \) (\( \frac{n}{9} + n \sqrt{n} \)) + \( 2^{93} \)
Problem/Ansatz:
Bei Master-Theorem ist es ja so, dass die Zahl vor dem T das a ist und die Zahl die man durch n teilt, das b ist. Die restliche Funktion ist dann f(n). Also in diesem Fall
f (n) = \( \sqrt{7n} \) (\( \frac{n}{9} + n \sqrt{n} \)) + \( 2^{93} \)
b = 4
a = 16.
logba = log4 16 = 2 .
Also ist (n + Epsilon) = (n² + Epsilon)
Jetzt muss also nur noch gecheckt werden ob, n² + epsilon größer, kleiner oder gleich f (n) ist. Und genau da liegt der Hund in der Petersilie.
Warum tut das Tier das? Weil ich nicht weiß, wie man f (n) = \( \sqrt{7n} \) (\( \frac{n}{9} + n \sqrt{n} \)) + \( 2^{93} \) geschickt vereinfachen soll, so dass man es mit n² vergleichen kann. Ich habe probiert, es soweit zu vereinfachen, aber weiter schaff ich's einfach nicht, um es mit n² zu vergleichen.
\( \sqrt{7} \) n² + \( \frac{\sqrt{7n}n}{9} \) + \( 2^{93} \)
Danke und einen schönen Freitag (Rest-)Abend noch.
