Hallo Leute, ich brauche eure Hilfe bei der folgenden Aufgabe: Ich soll für die Rekursionsgleichung
\( T(n) = 3 \cdot T\left(\left\lfloor \frac{n}{2} \right\rfloor \right) + \frac{n^2 \cdot \log_2(n)}{\sqrt{n}}, \)
mit den Anfangsbedingungen \( T(2) = T(1) = 1 \), eine möglichst einfache Funktion \( g(n) \) finden, sodass \( T(n) = \Theta(g(n)) \).
Dazu verwende ich das Mastertheorem. Demnach sind:
\( a = 3 \),
\( b = 2 \),
\( f(n) = \frac{n^2 \log_2(n)}{\sqrt{n}} = n^{3/2} \log_2(n) \).
Der rekursive Teil wäre dann \( n^{\log_2(3)} \approx n^{1.585} \).
Wenn wir nun \( f(n) \) mit dem rekursiven Teil vergleichen, fällt auf, dass der dominierende Faktor in \( f(n) \) \( n^{3/2} \) ist, was kleiner ist als der rekursive Teil. Das heißt, wir müssen den ersten Fall des Mastertheorems verwenden, weil \( f(n) \) langsamer wächst als der rekursive Teil. Also muss folgendes gezeigt werden:
\( f(n) \in O\left(n^{\log_2(3) - \varepsilon}\right) \quad \text{für ein } \varepsilon > 0. \)
Nur habe ich genau an dieser Stelle meine Schwierigkeiten. Ich bin immer noch unsicher, wie ich das beweisen soll.
