0 Daumen
230 Aufrufe

Aufgabe:

Löse folgende Rekurrenz im Θ-Kalkül:

T(n) = 28n + 4T(n/4), T(1) = 3.1415

mit n = 4k  

und k in ℕ<0


Problem/Ansatz:


Mein Ansatz wäre das ganze mit dem Master-Theorem zu lösen, allerdings hatte ich als Anfangswert T(1) bisher immer nur ganzzahlige Werte angegeben, wie gehe ich hier vor?

Avatar von

1 Antwort

0 Daumen

Mein Ansatz wäre das ganze mit dem Master-Theorem zu lösen, allerdings hatte ich als Anfangswert T(1) bisher immer nur ganzzahlige Werte angegeben, wie gehe ich hier vor?

Ist der Startwert überhaupt so wichtig für das asymptotische Wachstum?

Ich kenne das Master-Theorem so:

Sei \( a \geq 1, c \geq 2, d \geq 0 \) und \( T(n) \) durch \(T(n)=a\cdot T\left(\frac{n}{c}\right)+f(n)\) für \(n>1\) und \(T(1)=d\) mit einer Funktion \( f: \mathbb{N} \rightarrow \mathbb{R}_{+} \) gegeben.

Für \( n=c^{k} \) (mit \( k \in \mathbb{N} \) ) wächst \( T(n) \) asymptotisch gemäß

\( T(n) \in\left\{\begin{array}{ll} \Theta\left(n^{\alpha}\right)=\Theta(f(n)) & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a<c^{\alpha}, \\ \Theta\left(n^{\log _{c} a} \log n\right) & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a=c^{\alpha}, \\ \Theta\left(n^{\log _{c} a}\right), & \text { falls } f(n) \in \Theta\left(n^{\alpha}\right) \text { mit } a>c^{\alpha} . \end{array}\right. \)

Avatar von 28 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
0 Antworten
0 Daumen
0 Antworten
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community