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.
