Master-Theorem, Rekursionsgleichung...

Question

Bestimmen Sie für die Rekursionsgleichung

T(n)= 9*T(n/3) + n² + √n + 3*n + 3

die Komplexitätsklasse Θ mit Hilfe des Master-Theorems. Begründen Sie Ihre Antwort.

Answer 1

Wir haben die Rekursionsgleichung

$$T(n)= a T\left( \frac{n}{b} \right)+f(n)$$

wobei:

$$a=9 \geq 1 \\ b=3>1 \\ f(n)=n^2+ \sqrt{n}+3n+3$$

$$n^{\log_b a}=n^{\log_3 9}=n^{\log_3 3^2}=n^2$$

Außerdem haben wir dass:

 $$f(n)=n^2+ \sqrt{n}+3n+3= \Theta(n^2)$$

Also:

$$f(n)=\Theta(n^{\log_b a})$$


Was haben wir also vom 2ten Fall vom Master theorem?

Comments

T(n) ∈ Θ(n² *log(n) ) ?

---

Genau!  Denn vom 2ten Fall vom Master Theorem haben wir dass $$T(n) \in \Theta(n^{\log_b a} \log n)$$

---

Vielen Dank nochmal! :-) Wärst du so nett und würdest mir bei der folgenden Aufgabe helfen?

https://www.mathelounge.de/250302/pumping-lemma-beweis-kontextfrei?show=250479#c250479