In dieser Aufgabe wird nach der Laufzeitkomplexität dieser rekursiven Funktion gesucht. Man kann dies lösen, indem man für T(n) = a * T(n/b) + n^d in diesem Fall 1 < d < 2 abschätzt und erhält O(n^3) mit dem Master-Theorem.

Ich möchte diese Aufgabe aber mathematisch korrekt lösen, weshalb ich versucht habe zu substituieren, um das Master-Theorem anwenden zu können. Anscheinend habe ich mich aber irgendwo vertan, wo liegt mein Fehler?

Das Master-Theorem habe ich mit angehängt und wurde für a > 0, b > 1, d >= 0, n eine natürliche Zahl, bereits bewiesen. ( O entspricht logischerweise groß O, also einem der Landau-Symbole)