Rekursionsbaum?

Wir haben folgenden Rekursionsgleichung T(n) = 2T(n/2) + T(n/3) + n^2

Die vorgegebene Lösung ist diese:

n^2 verstehe ich ja, aber warum gehen 3 Pfade von dem ersten aus, ich hätte jetzt gedacht das müssten zwei sein und warum teile ich dann durch 4,4,9. Kann mir das jemand bitte erklären? Danke im Voraus

Answer 1

[eterneladam]

Die erste Frage kann ich dir nicht beantworten, wenn da z.B. n statt 2 stünde würde es ja schwierig ... aber n^2 / 4 entsteht durch einsetzen von n/2 in die Rekursion als letzter Summand in der Rekursionsgleichung.