---

Geschrieben von maumau am 02.04.2014 um 16:44:

  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.

---

Geschrieben von maumau am 03.04.2014 um 12:31:

 

2n/3 = n/(1/2) -> Höhe des Baumes = log_(1/2)(n). Korrekt?