Rekursiver Aufruf - Was geht da eigentlich vor sich?

[3_of_8]

Also inherited selbst meinte irgendwas von n log n, aber wenn ich mir das so ansehe, sieht es nach was anderem aus.

Er hat - je nachdem, ob n gerade oder ungerade ist - 2 oder 3 Rekursionsbäume bei jedem Funktionsaufruf und die Rekursionstiefe ist in etwa ld n. Daraus ergibt sich als untere Grenze O(2^(ld n))=O(n) und als obere Grenze O(3^(ld n))=O(3^((log3 n)/(log3 2))=O(n), also O(n)... wenn ich mich jetzt nicht verrechnet habe...