0 Daumen
175 Aufrufe

Aufgabe:

a)
\( \begin{array}{l} T(1)=1 \\ T(n)=2 \cdot T\left(\frac{n}{4}\right)+n+4 \quad \text { für } n>1 \end{array} \)
b)
\( \begin{array}{l} T(1)=1 \\ T(n)=9 \cdot T\left(\frac{n}{3}\right)+n \cdot \sqrt{n} \quad \text { für } n>1 \end{array} \)
c)
\( \begin{array}{l} T(1)=1 \\ T(n)=16 \cdot T\left(\frac{n}{2}\right)+12 \cdot n^{4}+16 \cdot n^{3}+100 \quad \text { für } n>1 \end{array} \)
d)
\( \begin{array}{l} T(1)=1 \\ T(n)=6 \cdot T\left(\frac{n}{6}\right)+\frac{n}{2} \quad \text { für } n>1 \end{array} \)
e)
\( \begin{array}{l} T(1)=1 \\ T(n)=8 \cdot T\left(\frac{n}{4}\right)+\frac{n^{2}}{6}+n \cdot \sqrt{n} \quad \text { für } n>1 \end{array} \)


Problem/Ansatz:

Bestimmen Sie mithilfe des Mastertheorems die beste mögliche O-Klasse für folgende Rekursionsgleichungen.
Geben Sie zusätzlich an, welches p Sie gewählt haben. Begründen Sie, warum weder durch eine andere Wahl
von p, noch durch die Anwendung eines anderen Falls des Mastertheorems eine bessere O-Klasse erreicht werden
kann.

Avatar von

Also für die \(\mathcal{O}\)-Klasse muss man doch nur einsetzen - wo liegt die Schwierigkeit?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community