Mastertheorem Rekursionsgleichung Fall 3

Question

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.

Answer 1

Ohne den Text gelesen zu haben sollte die letzte Ungleichung leicht zu zeigen sein.

Z.B per Vollständiger Induktion mit Induktions-Anfang n=4 und c=1/3

Answer 2

Das ist doch trivial und geht sogar ohne vollständige Induktion:

$9\cdot 3^{\frac{n}{4}}\leq c\cdot 3^{n}$

$3^{2+\frac{n}{4}}\leq c\cdot 3^{n}$

$3^{2-\frac{3}{4}n}\leq c$

Für $n\geq 3$ kann man dann $c<1$ finden.

Comments

Vielen Dank für deine Hilfe! Ich hätte da nur eine Verständnisfrage:

Wenn wir $a \cdot f(n/b)$ schreiben, meinen wir dann wirklich $9 \cdot 3^{n/4}$?
Ich habe nämlich damals das von der Tafel abgeschrieben:

$a \cdot f(n/b) = 9 \cdot \frac{3^n}{4} = \frac{9}{4} \cdot 3^n$

Und wurde dann auf dieser Basis bewiesen, aber macht das wirklich Sinn?