+2 Daumen
1,3k Aufrufe

Bestimmen Sie für die Rekursionsgleichung

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


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

1 Antwort

+1 Daumen

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?

Avatar von 1,5 k

T(n) ∈ Θ(n2 *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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community