Aufgabe:
In diesem Aufgabenblatt sollen Sie das Auflisen von rekursiven Zeitgleichungen üben. Zeigen Sie eine möglichst scharfe asymptotische obere Schranke für folgende rekursive Zeitgleichungen durch iteriertes Einsetzen (es gilt jeweils T(n) = O(1) fur n ≤ 2):
1. Gegeben seien zwei Algorithmen A und B. Die Laufzeiten der Algorithmen sind durch rekursive Zeitgleichungen beschrieben: \( T_A(n) = 7 T_A(n/2)+n^2 \) und \( T_B(n) = αT_B(n/4)+n^2 \). Was ist der größte ganzzahlige Wert fur α, sodass Algorithmus B asymptotisch schneller ist als Algorithmus A?