Bei einem Tischtennisturnier nehmen n Spieler teil. In jeder Runde spielen die Teilnehmer in Paaren. Die Verlierer scheiden jeweils aus. Falls in einer Runde eine ungerade Anzahl von Spielern vorhanden ist, dann kommt genau ein Teilnehmer eine Runde weiter, ohne zu spielen. Gesucht ist die Anzahl der Runden T(n), die notwendig ist, um den Sieger zu ermitteln. Dies führt zu folgender Rekurrenz.
T(1) = 0
T(n) = T(⌈n/2⌉) + 1.
1)
Lösen Sie diese Rekurrenz exakt
a)
zunächst für den Spezialfall n = 2k, k ∈ ℕ,
Hinweis: Iterationsmethode
b)
für beliebige n ∈ ℕ.
Hinweis: Substitutionsmethode(Bilde eine Vermutung für die Lösung und beweise diese per Induktion).
2)
Bestimmen Sie das größenordnungsmäßige Wachstum (Θ) von T(n) mit Hilfe des Master-Theorems, und vergleichen Sie dies mit den in 1) bestimmten Lösungen.
3)
Lösen Sie die folgende Rekurrenz (Θ).
T(1) = 0
T(n) = T(⌊n/2⌋) + n.
