Zeigen Sie mit Hilfe des Master-Theorems scharfe asymptotische Schranken für folgende Rekurrenzen.

Question

Master-Theorem (einfache Form): Für positive Konstanten $a, b, c, d$, sei $n=b^{k}$ für ein $k \in \mathbb{N}$.
$r(n)=\left\{\begin{array}{ll} a & \text { falls } n=1 \text { Basisfall } \\ c n+d r(n / b) & \text { falls } n>1 \text { teile und herrsche. } \end{array}\right.$
Es gilt
$r(n)=\left\{\begin{array}{ll} \Theta(n) & \text { falls } d<b \\ \Theta(n \log n) & \text { falls } d=b \\ \Theta\left(n^{\log _{b} d}\right) & \text { falls } d>b \end{array}\right.$

Aufgabe: Zeigen Sie mit Hilfe des Master-Theorems scharfe asymptotische Schranken für folgende Rekurrenzen.

b) $B(1):=1$ und für $n=3^{k}, k \in \mathbb{N}: B(n)=9 B(n / 3)+4 n$

Ich habe für d in Θ(n^log_b^d ) 9 eingesetzt, verstehe nicht warum in der Musterlösung 4 eingesetzt wurde:

b) $a=1, b=3, c=4, d=9 \stackrel{d \gg b}{\Rightarrow} T(n)=\Theta\left(n^{\log _{3} 4}\right)$

Comments

Frag doch mal jemand vom Lehrpersonal. Ich verstehe es jedenfalls auch nicht.