Aufgabe:
Text erkannt:
Rekursive Algorithmen
Rekursionsgleichung für die Laufzeit der binären Suche:
\( T(n)=\left\{\begin{array}{ll} b+T\left(\frac{n-1}{2}\right) & \text { falls } n>0, \\ a & \text { sonst. } \end{array}\right. \)
Folgende Vermutung für die geschlossen Form aufgestellt: \( T(n)=\log _{2}(n+1) \cdot b+a \)
a) Beweisen Sie mittels vollständiger Induktion, dass die geschlossene Form gilt. Bedenken Sie, dass wir vereinfachend annehmen, dass \( n=2^{k}-1 \) ist und daher die Induktion auch über \( k \) vollzogen werden kann.
b) Wie kann die Laufzeit für \( n \) abgeschätzt werden, die sich nicht als \( 2^{k}-1 \) darstellen lassen? Hinweis: Die Kostenfunktion ist monoton.
Problem/Ansatz:
Hey ich komme bei dieser Aufgabe leider nicht weiter. Kann mir hier jemand weiterhelfen? Vielen Dank im voraus
