0 Daumen
728 Aufrufe

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?

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community