2n/3 = n/(1/2) -> Höhe des Baumes = log_(1/2)(n). Korrekt?
maumau
Höhe von Rekursionsbäumen
Meine Frage:
Wie bestimme ich die Höhe eines Rekursionsbaumes?
Meine Ideen:
Bei Rekursionen wie die von Mergesort T(n) = 2T(n/2) + n ist die Höhe log_2(n) . Vermutlich wegen den rekursiven Aufrufen mit jeweils n/2 (?). Bei T(n) = 3T(n/4) + cn^2 ist die Höhe demnach log_4(n). Das das richtig ist, habe ich durch ein bisschen googlen herausgefunden. Aber wie ist die Höhe wenn T(n) = 3T(2n/3) + O(1) ist und wie bestimme ich diese? Hier kann man die Basis des Logarithmus nicht einfach aus dem rekursiven Aufruf ablesen.
