Hallo, ich habe ein Problem bei folgender Aufgabe:
Wir betrachten drei Rekursionsgleichungen der folgenden Form.
T(n) = {a • T(n/3) + n^d , falls n > 1
{1 , falls n = 1
Bestimmen Sie mit dem Master-Theorem möglichst gute asymptotische obere Schranken für T zu den folgenden Parametrisierungen.
a) a=9 und d=2
b)a=9 und d=1
c)a=2 und d=2
Beweisen Sie ferner die Korrektheit Ihrer Schranke für den Fall a=9 und d=2 (ohne das Master-Theorem zu verwenden) für Eingaben der Länge n = 3k ≥ 1 durch vollständige Induktion nach k.
Wie löse ich am besten diese Aufgabe?
Vielen Dank im voraus :)
