Master Theorem richtig anwenden

Question

ich habe eine Aufgabe, bei der ich das Master-Theorem anwenden soll. Nach langen hin und her und vielen Fragezeichen in meinem Kopf, bin ich auf folgende Lösung gekommen und würde gerne wissen, ob das so richtig ist:

a) T(n) = 9 T(n/3) + n => T(n) = Θ (n^2)

b) T(n) = T(2n/3) + 1 => T(n) = Θ (log(n))

c) T(n) = 9 T(n/5) + n log^14 (n) => T(n) = Θ (n^{1,365} log(n)) (hier habe ich Logarithmus von 9 zur Basis 5 gerundet)

d) T(n) = 2 T(n/2) + n log(n) => T(n) = Θ (n log (n))

Answer 1

Deine Ergebnisse passen. Ich würde an Deiner Stelle allerdings noch \(\log_2\) statt \(\log\) schreiben.

Zur Kontrolle: https://books.google.de/books?id=6eIPgTo8AaIC&pg=PA25#v=onepage&q&f=false