Hallo Leute, ich brauche eure Hilfe bei der folgenden Aufgabe:
Ich soll für die Rekursionsgleichung \( T(n) = 9 \cdot T\left( \lceil \frac{n}{4} \rceil \right) + 3^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 = 9 \)
\( b = 4 \)
\( f(n) = 3^n \)
Der rekursive Teil ergibt \( n^{\log_b a} = n^{\log_49} \).
Der nicht-rekursive Teil ist \( f(n) = 3^n \).
Da \( f(n) = 3^n \) exponentiell wächst und \( n^{\log_49} \) nur polynomiell wächst, ist klar, dass \( f(n) \) dominiert, und somit muss man den Fall 3 des Mastertheorems verwenden. Um das zu zeigen, muss gelten:
\( f(n) = \Omega(n^{\log_b a + \epsilon}) \)
Das bedeutet, es existiert eine Konstante \( a \in \mathbb{R}^+ \) und ein \( n_0 \in \mathbb{N} \), sodass für alle \( n \geq n_0 \):
\( 3^n \geq a \cdot n^{\log_49 + \epsilon} \)
Wählt man \( \epsilon = 1 \) und \( a = 1 \), so ist die Aussage wahr und es gilt: \( f(n) = 3^n \in \Omega(n^{\log_49 + 1}) \).
Nun muss auch gezeigt werden, dass es eine Konstante \( c < 1 \) gibt, sodass die folgende Ungleichung für ausreichend große \( n \) gilt:
\( 9 \cdot f\left( \frac{n}{4} \right) \leq c \cdot f(n) \)
An dieser Stelle bin ich jedoch nicht wirklich weitergekommen und habe Schwierigkeiten, zu zeigen, dass
\( 9 \cdot 3^{n/4} \leq c \cdot 3^n \) gilt.
