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.